Etter å ha løst delmengdesumproblemet (Subset Sum problem) i $O(2^{0.49n})$ tid, vil Little Cyan Fish at du skal løse følgende oppgave.

Little Cyan Fish har $n$ kort. Det $i$-te kortet ($1 \le i \le n$) har et ikke-negativt heltall $a_i$ skrevet på seg.

For hver delmengde $S \subseteq [n]$ av kortindekser, der $[n] = \{1, 2, \ldots, n\}$, noterer han summen av heltallene på de valgte kortene, det vil si $\sum_{i \in S} a_i$. Summen for den tomme delmengden er $0$. Ulike delmengder noteres hver for seg, selv om summene deres er like.

Etter å ha vurdert alle de $2^n$ delmengdene, sorterer han disse $2^n$ summene i ikke-avtakende rekkefølge og betegner dem med $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish vil at du skal finne den største differansen mellom to påfølgende summer, det vil si

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

Inndata

Det er flere testtilfeller. Den første linjen i inndataen inneholder ett enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen ett enkelt heltall $n$ ($1 \le n \le 10^6$), som angir antall kort. Den andre linjen inneholder $n$ heltall $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), som angir heltallene som er skrevet på kortene.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder ett enkelt heltall, som angir den største differansen mellom to påfølgende summer.

Eksempel

Inndata 1

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

Utdata 1

0
5
1
4

Forklaring

I det første testtilfellet i eksempelet er begge delmengdesummene $0$, så svaret er $0$.

I det andre testtilfellet i eksempelet er de sorterte delmengdesummene $0, 2, 3, 5, 10, 12, 13, 15$. Den største differansen er $5$, mellom $5$ og $10$.

I det tredje testtilfellet i eksempelet er de sorterte delmengdesummene $0, 1, 1, 2, 3, 4, 4, 5$. Svaret er $1$.

I det fjerde testtilfellet i eksempelet er de sorterte delmengdesummene $0, 0, 4, 4, 4, 4, 8, 8$. Svaret er $4$.