Решив задачу о сумме подмножества за время $O(2^{0.49n})$, Little Cyan Fish хочет, чтобы вы решили следующую задачу.

У Little Cyan Fish есть $n$ карточек. На $i$-й карточке ($1 \le i \le n$) написано неотрицательное целое число $a_i$.

Для каждого подмножества индексов карточек $S \subseteq [n]$, где $[n] = \{1, 2, \ldots, n\}$, он записывает сумму чисел на выбранных карточках, то есть $\sum_{i \in S} a_i$. Сумма для пустого подмножества равна $0$. Различные подмножества записываются отдельно, даже если их суммы совпадают.

Рассмотрев все $2^n$ подмножеств, он сортирует эти $2^n$ сумм в порядке неубывания и обозначает их через $s_0, s_1, \ldots, s_{2^n-1}$. Little Cyan Fish хочет, чтобы вы нашли максимальную разность между двумя соседними суммами, то есть

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

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T$), обозначающее количество наборов входных данных.

Для каждого набора входных данных первая строка содержит одно целое число $n$ ($1 \le n \le 10^6$), обозначающее количество карточек. Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), обозначающих числа, написанные на карточках.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^6$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — максимальную разность между двумя соседними суммами.

Примеры

Входные данные 1

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

Выходные данные 1

0
5
1
4

Примечание

В первом тестовом примере обе суммы подмножеств равны $0$, поэтому ответ равен $0$.

Во втором тестовом примере отсортированные суммы подмножеств равны $0, 2, 3, 5, 10, 12, 13, 15$. Максимальная разность равна $5$ — между числами $5$ и $10$.

В третьем тестовом примере отсортированные суммы подмножеств равны $0, 1, 1, 2, 3, 4, 4, 5$. Ответ равен $1$.

В четвёртом тестовом примере отсортированные суммы подмножеств равны $0, 0, 4, 4, 4, 4, 8, 8$. Ответ равен $4$.