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 ~\operatorname{mex}(T)~ into ~S~, where ~\operatorname{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 \leq t \leq 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 \leq n \leq 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 \leq f_i \leq 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 \leq 2~
• Subtask 2 (17 points): ~n \leq 20~
• Subtask 3 (7 points): ~f_i = 0~
• Subtask 4 (9 points): ~f_i \leq 1~
• Subtask 5 (20 points): ~f_i \leq 2000~
• Subtask 6 (9 points): ~f_0 \leq 10^{16}~ and ~f_j = 0~ (for all ~j \neq 0~)
• Subtask 7 (10 points): There exists a value ~i~ for which ~f_i \leq 10^{16}~ and ~f_j = 0~ (for all ~j \neq i~).
• Subtask 8 (23 points): No additional constraints