Розв'язавши задачу про суму підмножини за час $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$.