Después de resolver el problema de la suma de subconjuntos en tiempo $O(2^{0.49n})$, Little Cyan Fish quiere que resuelvas la siguiente tarea.

Little Cyan Fish tiene $n$ cartas. La $i$-ésima carta ($1 \le i \le n$) tiene escrito un número entero no negativo $a_i$.

Para cada subconjunto $S \subseteq [n]$ de índices de cartas, donde $[n] = \{1, 2, \ldots, n\}$, él registra la suma de los enteros en las cartas elegidas, es decir, $\sum_{i \in S} a_i$. La suma para el subconjunto vacío es $0$. Los subconjuntos diferentes se registran por separado, incluso si sus sumas son iguales.

Después de considerar todos los $2^n$ subconjuntos, ordena estas $2^n$ sumas en orden no decreciente y las denota por $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish quiere que encuentres la diferencia máxima entre dos sumas consecutivas, es decir,

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

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($1 \le n \le 10^6$), que indica el número de cartas. La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), que indican los enteros escritos en las cartas.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un solo entero, indicando la diferencia máxima entre dos sumas consecutivas.

Ejemplos

Entrada 1

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

Salida 1

0
5
1
4

Nota

En el primer caso de prueba de ejemplo, ambas sumas de subconjuntos son $0$, por lo que la respuesta es $0$.

En el segundo caso de prueba de ejemplo, las sumas de subconjuntos ordenadas son $0, 2, 3, 5, 10, 12, 13, 15$. La diferencia máxima es $5$, entre $5$ y $10$.

En el tercer caso de prueba de ejemplo, las sumas de subconjuntos ordenadas son $0, 1, 1, 2, 3, 4, 4, 5$. La respuesta es $1$.

En el cuarto caso de prueba de ejemplo, las sumas de subconjuntos ordenadas son $0, 0, 4, 4, 4, 4, 8, 8$. La respuesta es $4$.