Background

Problem Description

Alek Sui has solved $a_i$ problems of difficulty $i$ on a well-known OJ called Codeforces. He wants to solve some more problems so that $a_i$ forms an arithmetic progression with a non-positive common difference, because the resulting chart looks nice.

Although Alek Sui can solve 42 problems a day, he still wants to solve as few additional problems as possible to reach the goal. You need to find the minimum number of new problems he must solve.

You may assume that there are enough problems of every difficulty on the OJ.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains an integer $n$, the number of difficulty levels.
• The second line contains $n$ integers $a_i$.

Output Format

For each test case, output one integer per line, the answer.

6
2
822 1064
2
1064 822
4
1 3 4 2
4
2 4 3 1
6
2 6 2 1 4 4
9
9 9 8 2 4 4 3 5 3

242
0
6
4
17
25

Hint

For all testdata, $1\leq T\leq 100$, $1\leq n, \sum n\leq 10 ^ 5$, $1\leq a_i\leq 10 ^ 9$.

• Subtask 1 ($30$ points): $\sum n \leq 10 ^ 3$.
• Subtask 2 ($70$ points): no special constraints.

Source: NFLSPC #6 L by Alex_Wei

Translated by ChatGPT 5