El profesor Pedro un día decide seleccionar cuál es su mejor alumno, al cual apodará como intrépido volador. Para poder seleccionarlo, les propone el siguiente problema:

Dada una línea de ~n~ unidades (podrían ser metros, centímetros, pulgadas, pero vamos a llamarlas posiciones), se debe llegar desde la posición ~1~ hasta el final de la línea (la ~n~-ésima posición). En cada una de las ~n~ posiciones que tiene la línea hay un entero ~a_i~, el cual indica qué tan lejos se puede saltar desde la posición ~i~: si se encuentra en la posición ~i~ puede escoger un número entero ~d \in [0, a_i]~ y saltar hasta la posición: ~min(n, i + d)~.

Usted solamente debe responder con un entero: la menor cantidad de saltos que se debe dar para poder llegar desde ~1~ hasta ~n~.

Entrada

La primera línea de entrada contiene un entero ~t~ (~1 \le t \le 10^4~) — la cantidad de casos de prueba.

Cada caso de prueba comenzará con un entero ~n~ (~1 \le n \le 10^6~) — la cantidad de posiciones de la línea.

La siguiente línea contendrá ~n~ enteros ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — que representan el número marcado en cada metro de la línea.

Se garantiza que la suma de ~n~ en todos los casos no excederá ~10^6~.

Salida

Debe imprimir un solo número, la mínima cantidad de saltos para poder llegar a la posición ~n~, o ~-1~ en caso de que sea imposible llegar.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~\sum n \le 5000~	~60~	~-~
~2~	~-~	~40~	~1~

Ejemplos

Entrada de ejemplo 1

2
4
6 6 6 5
6
3 3 1 0 4 7

Salida de ejemplo 1

1
3

Entrada de ejemplo 1

1
7
5 3 5 5 3 6 2

Salida de ejemplo 1

2