Après avoir résolu le problème de la somme de sous-ensembles en temps $O(2^{0.49n})$, Little Cyan Fish souhaite que vous résolviez la tâche suivante.

Little Cyan Fish possède $n$ cartes. La $i$-ème carte ($1 \le i \le n$) porte un entier non négatif $a_i$.

Pour chaque sous-ensemble $S \subseteq [n]$ d'indices de cartes, où $[n] = \{1, 2, \ldots, n\}$, il note la somme des entiers inscrits sur les cartes choisies, c'est-à-dire $\sum_{i \in S} a_i$. La somme associée au sous-ensemble vide est $0$. Des sous-ensembles différents sont notés séparément, même si leurs sommes sont égales.

Après avoir considéré tous les $2^n$ sous-ensembles, il trie ces $2^n$ sommes par ordre croissant au sens large et les note $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish souhaite que vous trouviez la différence maximale entre deux sommes consécutives, c'est-à-dire

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

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($1 \le n \le 10^6$), indiquant le nombre de cartes. La deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), indiquant les entiers inscrits sur les cartes.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant la différence maximale entre deux sommes consécutives.

Exemples

Entrée 1

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

Sortie 1

0
5
1
4

Remarque

Dans le premier cas de test de l'exemple, les deux sommes de sous-ensembles valent $0$, donc la réponse est $0$.

Dans le deuxième cas de test de l'exemple, les sommes de sous-ensembles triées sont $0, 2, 3, 5, 10, 12, 13, 15$. La différence maximale est $5$, entre $5$ et $10$.

Dans le troisième cas de test de l'exemple, les sommes de sous-ensembles triées sont $0, 1, 1, 2, 3, 4, 4, 5$. La réponse est $1$.

Dans le quatrième cas de test de l'exemple, les sommes de sous-ensembles triées sont $0, 0, 4, 4, 4, 4, 8, 8$. La réponse est $4$.