[ol2] Greta's Game

Greta and Alice are the two permanent hosts of the hit comedy show "QuestExpert". For this season they invited n programmers to complete quests, set by Alice. After that they all meet in a studio to review how well they did and complete the final studio quest.

Today, the studio quest that Alice came up with is as follows: first, all n participants stand in a circle in order from 1 to n counter-clockwise. Then Alice holds some number of rounds. In each round, every participant writes down an integer on a piece of paper. After that, Alice checks the numbers and for each i from 1 to n, if the i-th participant's number is strictly larger than the number of the next participant in counter-clockwise order (participant number (i \bmod n) + 1), then the i-th and the (i \bmod n) + 1-st participants both receive one point. After all rounds are complete, Alice calculates the total number of points for each participant and reports them to Greta. It turned out that the i-th participant scored a_i points.

Greta thinks that math games are boring, and this one took too long. To prove her wrong, Alice decides to cheat a little and instead of telling Greta the real number of rounds, she will tell her the minimum possible number of rounds that could still result in the i-th participant scoring a_i points for each i.

Help Alice determine this number.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains a single integer n, denoting the number of participants (2 \le n \le 5 \cdot 10^5).

The second line contains n integers a_1, a_2, \ldots, a_n, denoting the final scores of the participants (0 \le a_i \le 10^9). It is guaranteed that those scores were achieved in the described game with at least one round.

It is guaranteed that the sum of n over all test cases does not exceed 5 \cdot 10^5.

Output

For each test case, output on a separate line the minimum number of rounds that could lead to the given scores.

Example

Input

5
2
3 3
3
2 2 2
4
1 2 4 3
5
0 2 3 5 4
6
5 8 3 10 14 4

Output

3
2
2
4
10