A long time ago, there was a big war. This war have two sides, one is The Schematics and the other one is The Unschematicszan. Joke is a respected general of The Schematics and is feared by The Unschematicszan. On every battle, Joke and his minions always win so the elite soldiers of The Unschematicszan can't fight him.

This war goes on until one day General Joke decides to end the war. At the same time, there are still N town that are under control of The Unschematicszan, numbered from 1 to N. In each town, there are P_i elite soldiers of The Unscehmaticszan that stands guard 24 hours a day. To take over a town, General Joke must bring at least the same number of minion as the number of elite soldiers guarding that town. After taking over a town, General Joke must leave at least a minion so that town doesn't get taken back by the Unschematicszan. The winner of the fight doesn't lose any soldier/minion in the fight. After a long thought, General Joke decides to take over the town starting from town number 1 to N and asks you to count the minimum number of minions that he must bring to successfully take over all the towns.

Input

First line is T, the number of test cases. For each test case, the first line is N, the number of towns occupied by The Unschematicszan. The next line is N numbers, representing P_i which is the number of elite soldiers on town i, starting from 1 to N.

Output

Minimum number of minions that Joke must bring to win.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100000
• 1 ≤ P_i ≤ 1000000

Example

Input:
1
5
1 2 5 4 2

Output:
7

Input file is huge, is faster I/O (scanf for C)