Setelah menyelesaikan masalah Jumlah Himpunan Bagian (Subset Sum problem) dalam waktu $O(2^{0.49n})$, Little Cyan Fish ingin Anda menyelesaikan tugas berikut.

Little Cyan Fish memiliki $n$ kartu. Kartu ke-$i$ ($1 \le i \le n$) memiliki sebuah bilangan bulat non-negatif $a_i$ yang tertulis di atasnya.

Untuk setiap himpunan bagian $S \subseteq [n]$ dari indeks kartu, dengan $[n] = \{1, 2, \ldots, n\}$, ia mencatat jumlah dari bilangan-bilangan bulat pada kartu yang dipilih, yaitu $\sum_{i \in S} a_i$. Jumlah untuk himpunan bagian kosong adalah $0$. Himpunan bagian yang berbeda dicatat secara terpisah, meskipun jumlahnya sama.

Setelah mempertimbangkan semua $2^n$ himpunan bagian, ia mengurutkan $2^n$ jumlah tersebut dalam urutan tidak menurun dan menotasikannya dengan $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish ingin Anda mencari selisih maksimum antara dua jumlah yang berurutan, yaitu,

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

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), yang menyatakan banyaknya kartu. Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), yang menyatakan bilangan-bilangan bulat yang tertulis pada kartu.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan selisih maksimum antara dua jumlah yang berurutan.

Contoh

Masukan 1

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

Keluaran 1

0
5
1
4

Catatan

Pada kasus uji contoh pertama, kedua jumlah himpunan bagian adalah $0$, sehingga jawabannya adalah $0$.

Pada kasus uji contoh kedua, jumlah himpunan bagian yang telah diurutkan adalah $0, 2, 3, 5, 10, 12, 13, 15$. Selisih maksimumnya adalah $5$, yaitu antara $5$ dan $10$.

Pada kasus uji contoh ketiga, jumlah himpunan bagian yang telah diurutkan adalah $0, 1, 1, 2, 3, 4, 4, 5$. Jawabannya adalah $1$.

Pada kasus uji contoh keempat, jumlah himpunan bagian yang telah diurutkan adalah $0, 0, 4, 4, 4, 4, 8, 8$. Jawabannya adalah $4$.