Eftir að hafa leyst hlutmengjasummuvandamálið (Subset Sum problem) á tímanum $O(2^{0.49n})$ vill Little Cyan Fish að þú leysir eftirfarandi verkefni.

Little Cyan Fish er með $n$ spil. Á $i$-ta spilinu ($1 \le i \le n$) stendur óneikvæð heiltala $a_i$.

Fyrir hvert hlutmengi $S \subseteq [n]$ af vísum spila, þar sem $[n] = \{1, 2, \ldots, n\}$, skráir hann summu heiltalnanna á völdu spilunum, þ.e. $\sum_{i \in S} a_i$. Summan fyrir tóma hlutmengið er $0$. Ólík hlutmengi eru skráð í sitthvoru lagi, jafnvel þótt summur þeirra séu jafnar.

Eftir að hafa skoðað öll $2^n$ hlutmengin raðar hann þessum $2^n$ summum í ekki-minnkandi röð og táknar þær með $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish vill að þú finnir mesta mismun á milli tveggja samliggjandi summa, þ.e.a.s.

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

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($1 \le n \le 10^6$), sem gefur til kynna fjölda spila. Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), sem gefa til kynna heiltölurnar sem skrifaðar eru á spilin.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna mesta mismun á milli tveggja samliggjandi summa.

Dæmi

Inntak 1

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

Úttak 1

0
5
1
4

Athugasemd

Í fyrsta prófunartilvikinu í dæminu eru báðar hlutmengjasummurnar $0$, svo svarið er $0$.

Í öðru prófunartilvikinu í dæminu eru röðuðu hlutmengjasummurnar $0, 2, 3, 5, 10, 12, 13, 15$. Mesti mismunurinn er $5$, á milli $5$ og $10$.

Í þriðja prófunartilvikinu í dæminu eru röðuðu hlutmengjasummurnar $0, 1, 1, 2, 3, 4, 4, 5$. Svarið er $1$.

Í fjórða prófunartilvikinu í dæminu eru röðuðu hlutmengjasummurnar $0, 0, 4, 4, 4, 4, 8, 8$. Svarið er $4$.