Minimum Jumps to Cross the River

You are given a river represented by a series of stepping stones. Each stone has a value that indicates the maximum distance you may jump forward from that stone. Your task is to determine the minimum number of jumps required to reach the last stone (i.e. cross the river) for each test case. If it is impossible to cross the river, output -1.

More formally, for a sequence of stones indexed from 0 to n-1 with corresponding jump values (a_0, a_1, \ldots, a_{n-1}), you start at stone 0. At each stone (i), you can jump to any stone (j) such that (i < j \leq i + a_i). Your goal is to reach stone (n-1) in the minimum number of jumps. If you cannot reach the last stone, return -1.

inputFormat

The input is read from standard input as follows:

The first line contains an integer T, the number of test cases. Each test case consists of two lines:

• The first line contains an integer N, representing the target index (i.e. the river is to be crossed when you reach stone index N-1).
• The second line contains at least N space-separated integers, where the first N integers represent the jump values on the stepping stones.

Note: Any extra numbers in the list beyond the first N can be ignored.

outputFormat

For each test case, output a single line with one integer: the minimum number of jumps required to reach the last stone. If it is not possible to cross the river, output -1.## sample

1
6
1 3 5 8 9 2 6 7 6 8 9

3