Pizano built an array $$$a$$$ of $$$n$$$ towers, each consisting of $$$a_i \ge 0$$$ blocks.

Pizano can knock down a tower so that the next $$$a_i$$$ towers grow by $$$1$$$. In other words, he can take the element $$$a_i$$$, increase the next $$$a_i$$$ elements by one, and then set $$$a_i$$$ to $$$0$$$. The blocks that fall outside the array of towers disappear. If Pizano knocks down a tower with $$$0$$$ blocks, nothing happens.

Pizano wants to knock down all $$$n$$$ towers in any order, each exactly once. That is, for each $$$i$$$ from $$$1$$$ to $$$n$$$, he will knock down the tower at position $$$i$$$ exactly once.

Moreover, the resulting array of tower heights must be non-decreasing. This means that after he knocks down all $$$n$$$ towers, for any $$$i \lt j$$$, the tower at position $$$i$$$ must not be taller than the tower at position $$$j$$$.

You are required to output the maximum $$$\text{MEX}$$$ of the resulting array of tower heights.

The $$$\text{MEX}$$$ of an array is the smallest non-negative integer that is not present in the array.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of towers.

The second line of each test case contains $$$n$$$ integers — the initial heights of the towers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

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 maximum $$$\text{MEX}$$$ of the final array.

Note

Explanation for the first test case.

$\text{[math]}$

Explanation for the second test case. Note that all towers were knocked down exactly once, and the final array of heights is non-decreasing.

$\text{[math]}$

Fallen Towers

Examples