部分和問題（Subset Sum problem）を $O(2^{0.49n})$ 時間で解決した後、Little Cyan Fish はあなたに次の問題を解いてほしいと考えています。

Little Cyan Fish は $n$ 枚のカードを持っています。$i$ 番目のカード（$1 \le i \le n$）には非負整数 $a_i$ が書かれています。

カードの添字の集合 $[n] = \{1, 2, \ldots, n\}$ の各部分集合 $S \subseteq [n]$ について、彼は選ばれたカードに書かれた整数の総和、すなわち $\sum_{i \in S} a_i$ を記録します。空集合に対する総和は $0$ です。異なる部分集合は、たとえそれらの総和が等しくても別々に記録されます。

すべての $2^n$ 個の部分集合を考慮した後、彼はこの $2^n$ 個の総和を広義単調増加順に並べ替え、それらを $s_0, s_1, \ldots, s_{2^n-1}$ と表します。Little Cyan Fish は、隣り合う二つの総和の差の最大値、すなわち

$$\max_{0 \le i < 2^n - 1} (s_{i+1} - s_i).$$

を求めてほしいと考えています。

入力

複数のテストケースが与えられます。入力の最初の行には、テストケースの個数を表す一つの整数 $T$（$1 \le T$）が含まれます。

各テストケースについて、最初の行にはカードの枚数を表す一つの整数 $n$（$1 \le n \le 10^6$）が含まれます。次の行には、カードに書かれた整数を表す $n$ 個の整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）が含まれます。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されています。

出力

各テストケースについて、隣り合う二つの総和の差の最大値を表す一つの整数を一行に出力してください。

入出力例

入力 1

4
1
0
3
2 3 10
3
1 1 3
3
0 4 4

出力 1

0
5
1
4

注記

一つ目のサンプルテストケースでは、二つの部分集合の総和はいずれも $0$ であるため、答えは $0$ です。

二つ目のサンプルテストケースでは、ソートされた部分集合の総和は $0, 2, 3, 5, 10, 12, 13, 15$ です。差の最大値は $5$ であり、これは $5$ と $10$ の間で達成されます。

三つ目のサンプルテストケースでは、ソートされた部分集合の総和は $0, 1, 1, 2, 3, 4, 4, 5$ です。答えは $1$ です。

四つ目のサンプルテストケースでは、ソートされた部分集合の総和は $0, 0, 4, 4, 4, 4, 8, 8$ です。答えは $4$ です。