G. Greta's Game
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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