STAR3CAS - THE WEIRD STAIRCASE

You are given a representation of a stair case with 'N' steps (0 to n-1). In every step a number x[i] (for ith step) is written on it. At each step you have two choices. Either you can to proceed to next step (i + 1) or you can jump x[i] steps from that step (i.e jump to i + x[i] th step). If the number written on the step is less than 0, you can come down that many number of steps or climb one step up.

Initially you are standing at the 0th step.

Find the minimum number of jumps needed to reach the top of the stair case.

If there is no way to reach the top of the stair case, print -1, else print the minimum number of jumps needed to reach the top of the staircase (nth step).

If a jump results in a step, which is greater than n, it is an invalid move.

Input

First line consists of 'T', the number of test cases. In every test case, the first line consists of 'n', the number of steps. The next line consists of n integers, x[0] to x[n-1].

Output

Print the minimum number of jumps required to reach the nth step. "Nth Step" is described in the problem statement.

Constraints

1 <= T <= 1000

1 <= n <= 20

-17 <= x[i] <= 17 and x[i] != 0

Example

Input:
2 
6 
-1 2 1 3 -3 3 
10 
5 1 1 1 6 -1 1 1 1 1 

Output:
3 
3

Added by:cegprakash
Date:2013-03-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

hide comments
2023-02-28 09:50:47 Simes
Minor confusion, as the diagram shows, there are actually N+1 steps, 0 to N.
2018-07-19 15:54:48
solved with [spoiler]!!! ac in one go!!!

Last edit: 2018-08-22 15:59:33
2018-03-27 06:38:36
The choice is always i+1, i+x[i], regardless of the value of x[i]. Like cegprakash said, this is not a greedy problem so don't follow 785227's comment; instead figure out what algo he might have confused BFS with.
2017-08-19 05:36:30
Easy problem with [spoiler]. Take care of negative elements in the array. You need to iterate through the [spoiler] loop as many times as many negative numbers are present in the array.Happy Coding ! :D

Last edit: 2018-08-22 16:00:12
2017-06-25 11:56:37 Sigma Kappa
Trivial.... should be moved to Tutorial. In place of this, tasks such as SPTTRN1-3 should be moved from tutorial to the classical.
2016-05-26 20:00:46 Mostafa Ali Mansour
My first recursion prblm

Last edit: 2016-05-26 20:01:25
2014-06-19 12:48:19 785227
My first ever bfs :)
2014-06-19 12:48:19 cegprakash
Don't be greedy and take care of cycles.
2014-06-19 12:48:19 pokemon
anymore test cases....?
2014-06-19 12:48:19 cegprakash
check for upper/lower limits
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.