All Submissions


Background

We have N circular rings from 0 to N-1. The area of the i-th ring is area[i]. Now we want to have progressively larger rings from the first ring to the last ring, so that each ring is bounded by the next ring. To make things simpler, let us assume that the i+1-th ring bounds the i-th ring if the area of (i+1)-th ring is atleast 1 unit more than the area of the i-th ring. So basically we want an array of progressively larger rings, such that the area of (i+1)-th ring is greater than or equal to (1 + area of i-th ring), for 0<=i<=N-2. You are given an array of area of rings. The areas may be in any order. To bring them to strictly ascending, you can increase or decrease the area of each circle by atmost C units. You cannot decrease the area of a circle to less than 1. All areas are initially given as integers and you can change them by intergral amounts only, i.e. after the change , the new area of each circle must be an integer. Also the change operation is expensive, a change of C has a cost proportional to C. Return the smallest possible non-negative integer C such that we can achieve our goal by allowing change of atmost C for every ring.

Input

1st line: An Integer T denoting the number of test cases.

Each test Case Contains: a number N on the first line (N is the number of rings). This is followed by N integers where the i-th integer is area of the i-th circle.

Output

Output a single line containing the value of C for this test case.

Sample Input


2
2
6 17
5
1 1 1 1 1


Sample Output


0
4


Explanation

In the first test case the areas are already progressively larger, so no change is required.
In the second test case, we can allow a change of atmost 4, thereby converting the areas into 1,2,3,4,5. The first one is kept unchanged, the rest are increaded by 1,2,3 and 4 units respectively (thus every change<=4 and area of any circle doesnot fall below 1)

Constraints

Each area lies between 1 and 1,000,000,000 (both inclusive).

Problem Setter : Souptik Sen

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0