Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

J. Time Limit
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In CCPC contests, you will get "Time Limit Exceeded" when your program tried to run during too much time. Setting suitable time limit for problems is vital to a contest.

Mr. Bread is preparing problems for a coming contest with his friends. For each problem, there will be a "Main Correct Solution" denotes the standard solution program written by the author. There will also be several "Correct Solutions" denote solution programs intended to pass.

Assume there are $$$n$$$ programs in total, labeled by $$$1,2,\dots,n$$$. The $$$1$$$-th program denotes the "Main Correct Solution" while others are "Correct Solutions". The $$$i$$$-th program runs in $$$a_i$$$ seconds.

According to the rules in Mr. Bread's mind, the time limit $$$x$$$ should meet all the rules below:

  • The constraint can't be too tight, which means $$$x\geq 3a_1$$$.
  • All the "Correct Solutions" should pass, which means $$$x\geq a_i+1$$$ for all $$$i\in[2,n]$$$.
  • $$$x$$$ should be the smallest even integer meeting the rules described above.

Please write a program to find the time limit $$$x$$$.

Input

The first line of the input contains an integer $$$T(1\leq T\leq 10)$$$, denoting the number of test cases.

In each test case, there is one integer $$$n(2\leq n\leq 10)$$$ in the first line, denoting the number of programs.

In the second line, there are $$$n$$$ integers $$$a_1,a_2,...,a_n(1\leq a_i\leq 10)$$$.

Output

For each test case, print a single line containing an integer, denoting the value of $$$x$$$.

Example
Input
2
2
1 3
2
1 4
Output
4
6