一直在你身旁

题目背景

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

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

题目描述

回到这座小镇后，她的新工作是维修电线。 现在，有一根电线坏了。已知电线长度可能为 $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

样例输入 #1

1
2
1 2

样例输出 #1

1

提示

【样例解释】

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

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