Dopo aver risolto il problema della somma di sottoinsiemi in tempo $O(2^{0.49n})$, Little Cyan Fish vuole che tu risolva il seguente compito.

Little Cyan Fish ha $n$ carte. Sulla $i$-esima carta ($1 \le i \le n$) è scritto un numero intero non negativo $a_i$.

Per ogni sottoinsieme $S \subseteq [n]$ di indici delle carte, dove $[n] = \{1, 2, \ldots, n\}$, egli registra la somma degli interi sulle carte scelte, ovvero $\sum_{i \in S} a_i$. La somma per il sottoinsieme vuoto è $0$. Sottoinsiemi diversi vengono registrati separatamente, anche se le loro somme sono uguali.

Dopo aver considerato tutti i $2^n$ sottoinsiemi, ordina queste $2^n$ somme in ordine non decrescente e le denota con $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish vuole che tu trovi la massima differenza tra due somme consecutive, ovvero

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

Dati di input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene un singolo intero $n$ ($1 \le n \le 10^6$), che indica il numero di carte. La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), che indicano gli interi scritti sulle carte.

È garantito che la somma di $n$ su tutti i casi di test non supera $10^6$.

Dati di output

Per ogni caso di test, stampa una singola riga contenente un singolo intero, che indica la massima differenza tra due somme consecutive.

Esempi

Input 1

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

Output 1

0
5
1
4

Note

Nel primo caso di test di esempio, entrambe le somme di sottoinsiemi sono $0$, quindi la risposta è $0$.

Nel secondo caso di test di esempio, le somme di sottoinsiemi ordinate sono $0, 2, 3, 5, 10, 12, 13, 15$. La differenza massima è $5$, tra $5$ e $10$.

Nel terzo caso di test di esempio, le somme di sottoinsiemi ordinate sono $0, 1, 1, 2, 3, 4, 4, 5$. La risposta è $1$.

Nel quarto caso di test di esempio, le somme di sottoinsiemi ordinate sono $0, 0, 4, 4, 4, 4, 8, 8$. La risposta è $4$.