There are n boxes on the circle. The boxes are numbered from 1 to n in clock wise 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 neighboring 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. 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

Note

There are two input files.

In the first input file, t=19, n<=1000, time limit=0.1 second;

In the second input file, t=3, n<=200000, time limit=2 seconds.

Warning: large input/output data, be careful with certain languages