喺用咗 $O(2^{0.49n})$ 時間複雜度解決咗子集和問題（Subset Sum problem）之後，小青魚想你解決下面呢道題目。

小青魚有 $n$ 張卡牌。第 $i$ 張卡牌（$1 \le i \le n$）上面寫住一個非負整數 $a_i$。

對於卡牌下標嘅每個子集 $S \subseteq [n]$（其中 $[n] = \{1, 2, \ldots, n\}$），佢會記錄所揀卡牌上面整數嘅總和，即係 $\sum_{i \in S} a_i$。空集對應嘅總和係 $0$。唔同嘅子集會分開記錄，就算佢哋嘅總和一樣都係噉話。

考慮晒所有 $2^n$ 個子集之後，佢將呢 $2^n$ 個總和按照非降序排好，並記做 $s_0, s_1, \ldots, s_{2^n-1}$。小青魚想你搵出兩個相鄰總和之間嘅最大差值，即係

$$\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$。