题目背景

转眼间，又到春天...
站在这里，我才发现，
原来，我的心，
已与那座被光玉守护的小镇相连。
......
“又到了一年春天啊...”
“看来，你已经准备留在这里了呢。”
“其实，我也没有什么远大的理想，只是努力地维持着现状...”
“不过，只要能实现自己的梦想，这又有什么关系啊...”
“但是现在，我真的是非常的开心。就像你说的那样，找到了很多快乐的事情...”
“我也和你一样，处在同一个世界。世界上没有一成不变的事物。 所以只要以其他方式找到自己的快乐就行了...”
“对啊，是时候开始新的生活了呢......”

“你对这个小镇真是执着呢...”
“因为，这里满是我不想忘记的回忆啊...”

题目描述

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

输入格式

本题有多组数据。

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

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

输出格式

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

1
2
1 2

1

提示

【样例解释】

买一根长度为 $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$ 的和。