Efter att ha löst delmängdssummeproblemet (Subset Sum problem) på tiden $O(2^{0.49n})$ vill Little Cyan Fish att du löser följande uppgift.

Little Cyan Fish har $n$ kort. På det $i$-te kortet ($1 \le i \le n$) står ett icke-negativt heltal $a_i$.

För varje delmängd $S \subseteq [n]$ av kortindex, där $[n] = \{1, 2, \ldots, n\}$, antecknar han summan av heltalen på de valda korten, det vill säga $\sum_{i \in S} a_i$. Summan för den tomma delmängden är $0$. Olika delmängder antecknas separat, även om deras summor är lika.

Efter att ha gått igenom alla $2^n$ delmängder sorterar han dessa $2^n$ summor i icke-avtagande ordning och betecknar dem med $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish vill att du hittar den största skillnaden mellan två på varandra följande summor, det vill säga

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

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($1 \le n \le 10^6$), som anger antalet kort. Den andra raden innehåller $n$ heltal $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), som anger heltalen skrivna på korten.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett enda heltal, vilket anger den största skillnaden mellan två på varandra följande summor.

Exempel

Indata 1

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

Utdata 1

0
5
1
4

Förklaring

I det första testfallet i exemplet är båda delmängdssummorna $0$, så svaret är $0$.

I det andra testfallet i exemplet är de sorterade delmängdssummorna $0, 2, 3, 5, 10, 12, 13, 15$. Den största skillnaden är $5$, mellan $5$ och $10$.

I det tredje testfallet i exemplet är de sorterade delmängdssummorna $0, 1, 1, 2, 3, 4, 4, 5$. Svaret är $1$.

I det fjärde testfallet i exemplet är de sorterade delmängdssummorna $0, 0, 4, 4, 4, 4, 8, 8$. Svaret är $4$.