Description

After returning to this town, her new job is to repair electric wires.
Now, one wire is broken. It is known that the wire length is one of $1,2,\cdots,n$. Now, she needs to find out the wire’s length.

She can spend $a_i$ money to buy a wire of length $i$. After buying this wire, she can know whether the required wire length is greater than $i$.
It is guaranteed that $a_1 \le a_2 \le \cdots \le a_n \le 10^9$.
Ask what is the minimum amount of money she must spend to guarantee that she can determine the required wire length.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

Then for each test case: one line contains an integer $n$, and the next line contains $n$ integers $a_1,a_2,\cdots,a_n$.

Output Format

Output $T$ lines, each line containing one answer.

1
2
1 2

1

Hint

[Sample Explanation]

Buy a wire of length $1$, and you can know whether the required length is greater than $1$. Then you can determine whether it is $1$ or $2$, so the answer is $1$.

Large sample link.

[Constraints]

This problem uses bundled testdata, with $4$ subtasks in total.

$(Subtask 1)(10\%)$, $n \le 15$.

$(Subtask 2)(10\%)$, $n \le 500$.

$(Subtask 3)(30\%)$, $n \le 2000$.

$(Subtask 4)(50\%)$, no additional constraints.

For $100\%$ of the testdata, $1 \le n,\sum n \leq 7100,T \leq 500$。$\sum n$ denotes the sum of $n$ over all test cases.

Translated by ChatGPT 5