限制

• 1000ms
• 512 MB

题目描述

lxy 最近很喜欢玩一个名为 《传送门》 的游戏，这个游戏中有 $n$ 个传送门，编号分别为 $1 \sim n$，而编号大于 $n$ 的位置都是空地。

第 $i$ 个传送门拥有 $1$ 点基础能量和 $a_i$ 点额外能量，穿过第 $i$ 个传送门会传送到编号为 $i + 1 + a_i$ 的位置处。

而传送门每进行一次传送，会消耗一点额外能量，即当穿过第 $i$ 个传送门后，这个传送门的额外能量会变为 $a_i - 1$。

当某个传送门的额外能量消耗完后，继续传送不会消耗基础能量，也就是说传送门不会失效。

每轮游戏玩家可以任选一个编号的传送门作为起点，然后连续穿过传送门直到传送到编号 $n$ 以外的空地。

当玩家将所有传送门的额外能量消耗完后，玩家就能获得胜利。

现在 lxy 想知道对于某一关游戏，告诉你每个传送门一开始的额外能量值，最少需要几轮游戏才能获胜？

输入格式

输入第一行包含一个正整数 $T$ 表示共有 $T$ 组测试数据

对于每组测试数据： 第一行包含一个正整数 $n$ 表示有 $n$ 个传送门 第二行包含 $n$ 个正整数 $a_1,a_2,a_3...a_n$，分别表示每个传送门的额外能量数量

输出格式

对于每组测试数据，输出获胜所需要最少的游戏轮数。

数据范围

对于 $30\%$ 的数据，$T == 1,2 \leq n \leq 500$

对于 $60\%$ 的数据，$T \leq 10, 2 \leq n \leq 5000$

对于 $100\%$ 的数据，$T \leq 50, 2 \leq n \leq 100000，1 \leq a_i \leq 10^9$

样例输入

2
2
1 2
5
0 0 0 0 0

样例输出

3
0

样例解释

对于第一组样例，需要进行 $3$ 轮游戏，起点编号分别为 $1,2,2$