You're given an array $a$ initially containing $n$ integers. In one operation, you must do the following:

• Choose a position $i$ such that $1 \lt i \le |a|$ and $a_i = |a| + 1 - i$, where $|a|$ is the current size of the array.
• Append $i - 1$ zeros onto the end of $a$.

After performing this operation as many times as you want, what is the maximum possible length of the array $a$?

Input

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

The first line of each test case contains $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$).

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

Output

For each test case, output a single integer — the maximum possible length of $a$ after performing some sequence of operations.

Note

In the first test case, we can first choose $i = 4$, since $a_4 = 5 + 1 - 4 = 2$. After this, the array becomes $[2, 4, 6, 2, 5, 0, 0, 0]$. We can then choose $i = 3$ since $a_3 = 8 + 1 - 3 = 6$. After this, the array becomes $[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$, which has a length of $10$. It can be shown that no sequence of operations will make the final array longer.

In the second test case, we can choose $i=2$, then $i=3$, then $i=4$. The final array will be $[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$, with a length of $11$.