On the way to Lanka, Ram and co encountered another interesting path. The path was laid with numbered rocks which were to be jumped over. The number denoted the maximum jump length that could be made by the person standing on that rock. For instance, if Ram was standing on a rock numbered 2, he could either make a jump of 1 and move to its immediate rock ahead of it or make a jump of 2 and move to the rock located 2 rocks ahead. Since, they were running out of time, Hanuman wanted to find out the minimum number of jumps they would have to make to reach the end of the path, given a list of numbers labeled on the rocks. Let us help Hanuman find the number.
INPUT: an integer T (1<=T<=1000) : number of testcases Each test case is represented by a number N(2<=N<=1000) denoting the number of rocks followed by an array of numbers rockNum[] labeled on those N rocks. The elements in the array rockNum[] will be less than or equal to N and greater than 0.
OUTPUT: For each test case, output the minimum number of jumps required to reach the goal(the last element of the array) from the starting position(first element of the array).
- In the first test case, Ram could make a jump as such (0,2,3,4 : jump 2 to index 2,jump 1 to index 3 and then jump 1 to index 4) or a jump as such (0,1,4 : jump 1 to index 1, jump 3 to index 4). Since the latter one involves the least number of jumps, the answer is 2.
- In the second test case, the optimal jump is (1,3,8,9). So the answer is 3 .
