当前没有测试数据。

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.

Khairy is a short guy, so he only sees the first row of the grid (High things may survive), also he is only impressed by at least two Gold Alloys adjacent to each other in a row, so if he found an Alloy alone in the row, he ignores it, else he would shout "WAL3AAAAAAAA".

Unfortunately all Gold Alloys that impress Khairy in the 1st row are destroyed and disappeard :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 fotune 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