题目描述

在一条数轴上，小明准备从起点 $0$ 跳到终点 $n-1$。

在数轴的每个点 $i$ ($0 \le i \le n-1$)上，都有一个限制跳跃长度的数值 $a[i]$，$a[i]$ 表示从 $i$ 向终点方向跳跃的 最大长度。

换句话说，如果小明在 $i$ 位置，那么小明能够跳跃的区间就是 $i \sim i+a[i]$，规定小明跳的位置都是整数。

小明想知道，它从起点。跳到终点 $n-1$ 的最小跳跃次数是多少。

输入格式

输入有 $T$ 组数据($1 \le T \le 50$)。

对于每组数据，输入有两行。

第一行一个整数 ;

第二行有 个整数，表示 $a[i]$,($0 \le i \le n-1$)

输出格式

输出小明跳到终点的最小跳跃次数。

若小明跳不到终点，输出 $-1$

样例

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

2 
3

样例解释：

对于第一组数据，小明从下标为 $0$ 跳到下标为 $1$ 的位置，跳 $1$ 步，然后跳 $3$ 步到达数组的最后一个位置。

数据范围

对于 $100\%$ 的数据保证：$2 \le n \le 10^6$，$1 \le a[i] \le 1000$。