Nachdem er das Teilmengensummenproblem in der Zeit $O(2^{0.49n})$ gelöst hat, möchte Little Cyan Fish, dass du die folgende Aufgabe löst.

Little Cyan Fish hat $n$ Karten. Auf der $i$-ten Karte ($1 \le i \le n$) steht eine nichtnegative ganze Zahl $a_i$.

Für jede Teilmenge $S \subseteq [n]$ von Kartenindizes, wobei $[n] = \{1, 2, \ldots, n\}$ ist, notiert er die Summe der ganzen Zahlen auf den ausgewählten Karten, d. h. $\sum_{i \in S} a_i$. Die Summe für die leere Teilmenge beträgt $0$. Verschiedene Teilmengen werden getrennt notiert, selbst wenn ihre Summen gleich sind.

Nachdem er alle $2^n$ Teilmengen betrachtet hat, sortiert er diese $2^n$ Summen in nichtabsteigender Reihenfolge und bezeichnet sie mit $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish möchte, dass du die maximale Differenz zwischen zwei aufeinanderfolgenden Summen findest, also

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

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($1 \le n \le 10^6$), die die Anzahl der Karten angibt. Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), die die auf den Karten stehenden ganzen Zahlen angeben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $10^6$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die die maximale Differenz zwischen zwei aufeinanderfolgenden Summen angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

0
5
1
4

Hinweis

Im ersten Beispieltestfall sind beide Teilmengensummen $0$, daher ist die Antwort $0$.

Im zweiten Beispieltestfall lauten die sortierten Teilmengensummen $0, 2, 3, 5, 10, 12, 13, 15$. Die maximale Differenz beträgt $5$, zwischen $5$ und $10$.

Im dritten Beispieltestfall lauten die sortierten Teilmengensummen $0, 1, 1, 2, 3, 4, 4, 5$. Die Antwort ist $1$.

Im vierten Beispieltestfall lauten die sortierten Teilmengensummen $0, 0, 4, 4, 4, 4, 8, 8$. Die Antwort ist $4$.