부분집합 합 문제(Subset Sum problem)를 $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$입니다.