F. Absolute Madness
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array of $$$n$$$ positive integers with the $$$i$$$th number being $$$2^{a_i}$$$ for a nonnegative integer $$$a_i$$$. You then perform the following operation $$$n-2$$$ times, leaving $$$2$$$ numbers in the array:

Choose two adjacent numbers in the array $$$a, b$$$, and replace them with their sum ($$$a+b$$$) or their difference ($$$a-b$$$).

Let $$$u, v$$$ be the final numbers remaining in the array. Find the minimum possible value of $$$|u| + |v|$$$.

Input

Each test contains multiple test cases. The first line of input contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of input test cases.

The first line of each test case contains $$$n$$$ ($$$2 \leq n \leq 5\times 10^5$$$) — the length of the array.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n}$$$ ($$$0 \leq a_i \leq n$$$) — the exponents of each element.

It is further guaranteed that the sum of $$$n$$$ over all test cases is at most $$$5\times 10^5$$$.

Output

For each test case, output the minimum possible value of $$$|u| + |v|$$$ in binary.

Example
Input
3
5
1 3 4 3 0
5
3 4 5 5 3
5
0 5 1 4 4
Output
11
10000
11
Note

For the first test case, the initial array is $$$s = [2, 8, 16, 8, 1]$$$. We can subtract $$$s[3]$$$ from $$$s[2]$$$ to give $$$s = [2, 8, 8, 1]$$$. We can then subtract $$$s[2]$$$ from $$$s[1]$$$ to give $$$s = [2, 0, 1]$$$. We can then add together the first two numbers to give $$$u = 2, v = 1$$$ and $$$|u| + |v| = 3 = 11_2$$$.

It can be shown that you cannot achieve values smaller than $$$16$$$ and $$$3$$$, respectively, for the other two test cases.