Frodo is on the quest to destroy the Lord of the Rings. But Frodo has to cross some dangerous blocks which have fire on them.
There are N blocks and Frodo starts from block 1, which doesn't have fire.
Each i-th block will have fire starting at time 0 and stopping at time $T[i]$. Of-course, $T[1] = 0$ as Frodo starts from block 1.
Frodo can step on a block only if it has no fire. Therefore, if the fire at block i ends at $T[i]$, he can step on it only at time $(T[i]+1)$ or greater.
Frodo can walk from block i to j in unit time, given that $i < j$ and there is no fire on blocks between i to j, including i and j.
What is the minimum time required to reach N-th block?

                                                  

Input:
First line consists of an integer t denoting the number of test cases
Each test case begins with N, number of blocks
Next line consist of N spaced integers denoting $T[i]$, the time at which fire on i-th block will stop

Constraints:
$1 ≤ t ≤ 10$
$1 ≤ N ≤ 100000$
$0 ≤ T[i] ≤ 1000000$
$T[1] = 0$

Output:
For each test case, print integer denoting minimum time required in a single line