Ratkaistuaan osajoukkosummaongelman (Subset Sum problem) ajassa $O(2^{0.49n})$ Little Cyan Fish haluaa sinun ratkaisevan seuraavan tehtävän.

Little Cyan Fishillä on $n$ korttia. Korttiin $i$ ($1 \le i \le n$) on kirjoitettu epänegatiivinen kokonaisluku $a_i$.

Jokaiselle korttien indeksien osajoukolle $S \subseteq [n]$, missä $[n] = \{1, 2, \ldots, n\}$, hän kirjaa muistiin valituissa korteissa olevien kokonaislukujen summan eli $\sum_{i \in S} a_i$. Tyhjän osajoukon summa on $0$. Eri osajoukot kirjataan erikseen, vaikka niiden summat olisivat yhtä suuret.

Käytyään läpi kaikki $2^n$ osajoukkoa hän järjestää nämä $2^n$ summaa ei-vähenevään järjestykseen ja merkitsee niitä $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish haluaa sinun etsivän suurimman erotuksen kahden peräkkäisen summan välillä, eli

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

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 10^6$), joka ilmoittaa korttien lukumäärän. Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), jotka ilmoittavat kortteihin kirjoitetut kokonaisluvut.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: suurimman erotuksen kahden peräkkäisen summan välillä.

Esimerkit

Syöte 1

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

Tuloste 1

0
5
1
4

Huomautus

Ensimmäisessä esimerkkitapauksessa molemmat osajoukkojen summat ovat $0$, joten vastaus on $0$.

Toisessa esimerkkitapauksessa järjestetyt osajoukkojen summat ovat $0, 2, 3, 5, 10, 12, 13, 15$. Suurin erotus on $5$, lukujen $5$ ja $10$ välillä.

Kolmannessa esimerkkitapauksessa järjestetyt osajoukkojen summat ovat $0, 1, 1, 2, 3, 4, 4, 5$. Vastaus on $1$.

Neljännessä esimerkkitapauksessa järjestetyt osajoukkojen summat ovat $0, 0, 4, 4, 4, 4, 8, 8$. Vastaus on $4$.