A great tournament of the game Bajt: Bitmingham has just taken place in Bajtowo. Exactly three players participate in a single game of Bajt: Bitmingham, and they must meet in one place to conduct the game.

As you probably know, there is only one long road in Bajtowo, along which there are $n$ buildings, numbered consecutively from $1$ to $n$.

For the convenience of the players, it has been established that if a trio of players lives in buildings with numbers $a$, $b$, and $c$, the game is held in the middle of these buildings, i.e., the building with the number that is the median of $a$, $b$, and $c$. In particular, if two players live in the same building $x$, then regardless of where the third player lives, the game will be held in building $x$.

You are preparing a summary of the tournament statistics. You know that every trio of players played against each other at most once. For each building, you know how many games were held in it: for building number $i$, it was $a_i$ games. However, you forgot to find out how many players were in the tournament...

Calculate the minimum possible number of players participating in the tournament that is not inconsistent with the information you have.

You must solve this problem for $t$ independent test cases.

Input

The first line of the input contains a number $t$ ($1 \le t \le 50$), representing the number of test cases.

Each test case is described by two lines. The first of these lines contains an integer $n$ ($1 \le n \le 200\,000$), representing the number of buildings in Bajtowo. The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$), representing how many games were held in consecutive buildings. You can assume that at least one value $a_i$ is positive.

The sum of $n$ over all test cases will not exceed $200\,000$.

Output

The output should contain $t$ lines, with the $i$-th line containing a single integer representing the minimum number of people who could have participated in the tournament.

Examples

Input 1

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

Output 1

3
9
5
6

Note

In the first test case, 3 players are needed to conduct one game. In the second test case, there are 57 games; 8 players are not enough, as there would then be only $\binom{8}{3} = 56$ different trios, so a ninth player is needed. In the third test case, one player could have lived in each building: in the second building, games were held between players from buildings 1, 2, 3; 1, 2, 4; and 1, 2, 5; in the third building, games were held between players from buildings 1, 3, 4; 1, 3, 5; 2, 3, 4; and 2, 3, 5; * in the fourth building, games were held between players from buildings 1, 4, 5; 2, 4, 5; and 3, 4, 5.

In the fourth test case, 5 players are not enough, because in some building there would be at most two of them, and that is not enough to find 4 trios with the appropriate median.