Sau khi giải quyết bài toán Tổng tập con (Subset Sum problem) trong thời gian $O(2^{0.49n})$, Little Cyan Fish muốn bạn giải quyết bài toán sau đây.

Little Cyan Fish có $n$ lá bài. Lá bài thứ $i$ ($1 \le i \le n$) có ghi một số nguyên không âm $a_i$ trên đó.

Với mỗi tập con $S \subseteq [n]$ các chỉ số lá bài, trong đó $[n] = \{1, 2, \ldots, n\}$, cậu ấy ghi lại tổng các số nguyên trên các lá bài được chọn, tức là $\sum_{i \in S} a_i$. Tổng của tập con rỗng là $0$. Các tập con khác nhau được ghi lại riêng biệt, ngay cả khi tổng của chúng bằng nhau.

Sau khi xét tất cả $2^n$ tập con, cậu ấy sắp xếp $2^n$ tổng này theo thứ tự không giảm và ký hiệu chúng là $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish muốn bạn tìm hiệu lớn nhất giữa hai tổng liên tiếp, tức là:

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

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 10^6$), cho biết số lượng lá bài. Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), cho biết các số nguyên được ghi trên các lá bài.

Dữ liệu đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên duy nhất, cho biết hiệu lớn nhất giữa hai tổng liên tiếp.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
5
1
4

Ghi chú

Trong bộ dữ liệu ví dụ đầu tiên, cả hai tổng tập con đều là $0$, vì vậy đáp án là $0$.

Trong bộ dữ liệu ví dụ thứ hai, các tổng tập con sau khi sắp xếp là $0, 2, 3, 5, 10, 12, 13, 15$. Hiệu lớn nhất là $5$, giữa $5$ và $10$.

Trong bộ dữ liệu ví dụ thứ ba, các tổng tập con sau khi sắp xếp là $0, 1, 1, 2, 3, 4, 4, 5$. Đáp án là $1$.

Trong bộ dữ liệu ví dụ thứ tư, các tổng tập con sau khi sắp xếp là $0, 0, 4, 4, 4, 4, 8, 8$. Đáp án là $4$.