The first line of input contains one positive integer i that represents the number of test cases that follow.

Each test case is described in two lines. The first line contains one integer N(1<=N<=1000 000): the number of cars that participate in the race. The second line holds a sequence of N integers A1,A2….An(0<=Ai<=10^9) that gives the number of overtakes performed by the respective cars.

The size of a single input file does not exceed 20MB.