We all know "Connect 4 Game", One day Khairy has a grid with infinite height and n numbers representing the number of discs in the ith column. It's guaranteed that no empty cells between any discs in the same column. for each disc in the grid if Khairy saw a disc on its left OR its right, he'll say "Wal3a". Given the N numbers, What's the maximum number that Khairy will say "Wal3a"!

Khairy is a small guy who likes gold very much, but he has a problem in his eyes and the word "WAL3A" (WAL3A in Arabic means "Firing"), whenever he likes something very much sooner or later it is destroyed by any means (Please don't impress him with something you want :|)

One day Khairy visited the National Museum and saw a Grid with infinite height and N columns and each column i contains Xi Gold Alloys. No empty cells between Alloys in the same column.

Unfortunately all Gold Alloys that impress Khairy in the 1st row are destroyed and disappeared :S, consequently the Alloys of the same columns above the destroyed Alloys fall to the the cell which is directly below it (each affected column height is decreased by 1 unit). Khairy continues saying "WAL3A" till he finds the first row not impressing anymore.

The example below Khairy would say "WAL3A" twice and 7 gold alloys are destroyed.

Of course the museum lost a fortune during Khairy's visit, so could you help the government find how many Gold Alloys are destroyed by Khairy.

Input

The first line of input contains an integer T (1 <= 20 <= T) followed by T test cases.

Each test case contains a positive integer N [1 <= N <= 10⁵] followed by N integers [0 <= X_i <= 10⁹] separated by spaces (see sample input for more clarification).

Output

For each test case output one line contains how many Gold Alloys are destroyed by Khairy.

Example

Input:
2
5
1 2 2 1 5
3
7 7 7

Output:
7
21