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.

Greta's Game

Examples