Description

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of flowers.

The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10 ^ 9$) — the heights of the flowers.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer — the number of seconds that will pass before $h_i=0$ for all $1 \le i \le n$.

4
3
1 1 2
2
3 1
1
9
5
7 4 4 3 2
 
 
 
 

4
3
9
7

Note

In the first test case, the flower heights change as follows: $[1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$.

In the second test case, the flower heights change as follows: $[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]$.