在以 $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$。