该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师准备参加跳远比赛。假设从位置$0$开始，每个位置$i$有一个最大跳跃距离$a_i$（即可以从位置$i$跳到$[i+1, i+a_i]$范围内的任意位置）。

请问，从位置$0$出发，至少需要跳跃多少次才能到达或超过位置$n$。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$，表示目标位置（数组长度为$n$，位置编号为$0$到$n-1$，目标是到达或超过$n$）。

第二行$n$个整数$a_i(1 \leq a_i \leq 10^5)$，表示位置$i$的最大跳跃距离。

Output

对于每组测试，输出一个整数，表示最少需要的跳跃次数。

Samples

2
5
2 3 1 1 4
10
1 3 2 1 1 2 5 4 2 3

3
6

Limitation

1s, 1024KiB for each test case.