// Author: @Drydock
use std::io::{self, Read};

fn main() {
    solve();
}

fn solve() {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = I::new(&s);
    let tt: usize = it.n();
    let mut o = String::new();
    for _ in 0..tt {
        let n: usize = it.n();
        let mut a: Vec<usize> = Vec::with_capacity(n);
        for _ in 0..n { a.push(it.n()); }
        let tgt = n;
        let w = (tgt + 64) / 64;
        let mut b = vec![0u64; w];
        b[0] = 1u64;
        for &v in &a {
            if v > tgt { continue; }
            let q = v / 64;
            let r = v % 64;
            let mut t = vec![0u64; w];
            if r == 0 {
                for i in 0..w {
                    if i + q < w {
                        t[i + q] |= b[i];
                    }
                }
            } else {
                for i in 0..w {
                    if i + q < w {
                        t[i + q] |= b[i] << r;
                    }
                    if i + q + 1 < w {
                        t[i + q + 1] |= b[i] >> (64 - r);
                    }
                }
            }
            for i in 0..w { b[i] |= t[i]; }
        }
        let mut ans = 0usize;
        'outer: for ssum in (0..=tgt).rev() {
            let idx = ssum / 64;
            let off = ssum % 64;
            if (b[idx] >> off) & 1u64 == 1u64 {
                ans = ssum;
                break 'outer;
            }
        }
        o.push_str(&format!("{}\n", ans));
    }
    print!("{}", o);
}

struct I<'a> { w: std::str::SplitWhitespace<'a> }

impl<'a> I<'a> {
    fn new(s: &'a str) -> Self { Self { w: s.split_whitespace() } 
    }
    fn n<T: std::str::FromStr>(&mut self) -> T { self.w.next().unwrap().parse().ok().unwrap() }
}