There are n boxes on the circle. The boxes are numbered from 1 to n (1 ≤ n ≤ 1000) in clockwise order. There are balls in the boxes, and the number of all the balls in the boxes is not greater than n.

The balls should be displaced in such a way that in each box there remains no more than one ball. In one move we can shift a ball from one box to one of it's neighbouring boxes.

Write a program that: reads from the standard input the number of boxes n and the arrangement of balls in the boxes, computes the minimal number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball, writes the result in the standard output.

Input

The first line of the input file contains an integer t representing the number of test cases (t ≤ 20). Then t test cases follows. Each test case has the following form:

• The first line contains one positive integer n - the number of boxes
• The second line contains n nonnegative integer separated by single spaces. The i-th number is the number of balls in the i-th box.

Output

For each test case, output one nonnegative integer - the number of moves necessary to displace the balls in such a way that in each box there remains no more than one ball.

Example

Input:
1
12
0 0 2 4 3 1 0 0 0 0 0 1

Output:
19