A multiset is a collection of elements similar to a set, where elements can repeat multiple times. For example, the following is a multiset: $\{0,0,1,2,2,5,5,5,8\}$.

Given a multiset $S$ defined on non-negative integers, and a target non-negative integer value $n$ such that $n$ does not belong to $S$, your goal is to insert $n$ into $S$ by using the following 3-step operation, repeatedly:

• Choose a (possibly empty) subset $T$ of $S$. Here, $T$ is a set of distinct numbers that appear in $S$.
• Erase elements of $T$ from $S$. (Remove only one copy of each element.)
• Insert $\mathrm{mex}(T)$ into $S$, where $\mathrm{mex}(T)$ is the smallest non-negative integer that does not belong to $T$. The name mex stands for "minimum excluded" value.

Your goal is to find the minimum number of operations to perform so that $n$ becomes part of $S$. Since the size of $S$ may be large, it will be given in the form of a list $(f_0,\dots ,f_{n-1})$ of size $n$, where $f_i$ represents the number of times that the number $i$ appears in $S$. (Recall that $n$ is the integer we are trying to insert into $S$.)

Input Specification

The first line contains a single integer $t$ $(1\le t\le 200)$ — the number of test cases. Each two of the following lines describe a test case:

The first line of each test case contains a single integer $n$ $(1\le n\le 50)$, representing the integer to be inserted into $S$.

The second line of each test case contains $n$ integers $f_0,f_1,\dots ,f_{n-1}$ $(0\le f_i\le {10}^{16})$, representing the multiset $S$ as mentioned above.

Output Specification

For each test case, print a single line containing the minimum number of operations needed to satisfy the condition.

Sample Input

2
4
0 3 0 3
5
4 1 0 2 0

Sample Output

4
10

Explanation

In the first example, initially, $S=\{1,1,1,3,3,3\}$ and our goal is to have $4$ in $S$. We can do the following:

• choose $T=\{\}$ then $S$ becomes $\{0,1,1,1,3,3,3\}$.
• choose $T=\{0,1,3\}$ then $S$ becomes $\{1,1,2,3,3\}$.
• choose $T=\{1\}$ then $S$ becomes $\{0,1,2,3,3\}$.
• choose $T=\{0,1,2,3\}$ then $S$ becomes $\{3,4\}$.

Constraints

• Subtask 1 (5 points): $n\le 2$
• Subtask 2 (17 points): $n\le 20$
• Subtask 3 (7 points): $f_i=0$
• Subtask 4 (9 points): $f_i\le 1$
• Subtask 5 (20 points): $f_i\le 2000$
• Subtask 6 (9 points): $f_0\le {10}^{16}$ and $f_j=0$ (for all $j\ne 0$)
• Subtask 7 (10 points): There exists a value $i$ for which $f_i\le {10}^{16}$ and $f_j=0$ (for all $j\ne i$).
• Subtask 8 (23 points): No additional constraints