Roy has a number of coins with him that he loves playing with by arranging them in the form of N stacks numbered sequentially. Lucy now gives him a task to make his arrangement of coins even more interesting. The arrangement will be interesting if the number of coins in the stacks are in strictly increasing order.

For this task Lucy gives Roy the option to modify his arrangement by increasing or decreasing the number of coins in each of the stack by atmost C coins. Also the number of coins in a stack should not fall below 1.

Your mission, should you choose to accept it, is to report the minimum C that helps Roy complete the assigned task.

Input
First line contains T, the number of test cases

Each test case contains two lines. The first line has a single integer N. The second line contains N space separated integers denoting the number of coins in the stacks initially.

Output
A single line for each test case containing the answer as explained in the statement.

Constraints
1 <= T <= 200
2 <= N <= 1000
The number of coins initially in each of the stack is between 1 and 1000000000.