gxy 的传送门 1485

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：10 AC：5 Score：100

Description

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

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

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

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

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

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

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

Input

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

对于每组测试数据：
第一行包含一个正整数 n 表示有 n 个传送门

第二行包含 n 个正整数 a_1,a_2,a_3...a_n，分别表示每个传送门的额外能量数量

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

对于 60\% 的数据，T <= 10, 2 <= n <= 5000

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

Output

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

Samples

input:

2 2 1 2 5 0 0 0 0 0

output:

3 0