Po rozwiązaniu problemu sumy podzbioru w czasie $O(2^{0.49n})$, Little Cyan Fish chce, abyś rozwiązał następujące zadanie.

Little Cyan Fish ma $n$ kart. Na $i$-tej karcie ($1 \le i \le n$) zapisana jest nieujemna liczba całkowita $a_i$.

Dla każdego podzbioru $S \subseteq [n]$ indeksów kart, gdzie $[n] = \{1, 2, \ldots, n\}$, zapisuje on sumę liczb całkowitych na wybranych kartach, czyli $\sum_{i \in S} a_i$. Suma dla podzbioru pustego wynosi $0$. Różne podzbiory są zapisywane osobno, nawet jeśli ich sumy są równe.

Po rozważeniu wszystkich $2^n$ podzbiorów sortuje on te $2^n$ sum w porządku niemalejącym i oznacza je przez $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish chce, abyś znalazł maksymalną różnicę między dwiema kolejnymi sumami, to znaczy

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

Wejście

Występuje wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą liczbę kart. Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), oznaczających liczby całkowite zapisane na kartach.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą maksymalną różnicę między dwiema kolejnymi sumami.

Przykład

Wejście 1

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

Wyjście 1

0
5
1
4

Uwagi

W pierwszym przykładowym przypadku testowym obie sumy podzbiorów wynoszą $0$, więc odpowiedzią jest $0$.

W drugim przykładowym przypadku testowym posortowane sumy podzbiorów to $0, 2, 3, 5, 10, 12, 13, 15$. Maksymalna różnica wynosi $5$, pomiędzy $5$ a $10$.

W trzecim przykładowym przypadku testowym posortowane sumy podzbiorów to $0, 1, 1, 2, 3, 4, 4, 5$. Odpowiedzią jest $1$.

W czwartym przykładowym przypadku testowym posortowane sumy podzbiorów to $0, 0, 4, 4, 4, 4, 8, 8$. Odpowiedzią jest $4$.