Description

回到这座小镇后，她的新工作是维修电线。
现在，有一根电线坏了。已知电线长度可能为 $1,2,\cdots,n$ 中的一个数。现在，她需要知道电线的长度。
她可以花费 $a_i$ 块钱购买长度为 $i$ 的电线。购买这根电线后，她能知道所需要的电线长度是否 大于 $i$。
保证 $a_1 \le a_2 \le \cdots \le a_n \le 10^9$。
问她至少要花多少钱才能保证知道需要电线的长度。

Input Format

本题有多组数据。

第一行为一个正整数 $T$ 表示数据组数。

接下来，每组数据，一行一个整数 $n$，接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

Output Format

$T$ 行，每行输出一个答案。

1
2
1 2

1

Hint

【样例解释】

买一根长度为 $1$ 的电线，就能知道需要的长度是否大于 $1$，也就能确定是 $1$ 还是 $2$，所以答案就是 $1$。

大样例链接。

【数据范围】

本题捆绑测试，共有 $4$ 个子任务。

$(Subtask 1)(10\%)$，$n \le 15$。

$(Subtask 2)(10\%)$，$n \le 500$。

$(Subtask 3)(30\%)$，$n \le 2000$。

$(Subtask 4)(50\%)$，没有任何额外限制。

对于100%的数据点, $1 \le n,\sum n \leq 7100,T \leq 500$。$\sum n$ 表示所有数据中 $n$ 的和。