21363_ChutterandLadder

Here is a simpler version of the interesting game "Chutter and Ladder":

Given a sequence of small grids, numbered from 0 to n-1. As the player of this game, your starting position is grid 0, and your destination is grid n-1. Each time you can drop a dice and move 1-6 steps forward according to the number on top of the dice. As the dice is perfect, each number from 1 to 6 can evenly show on top of the dice.

However, each grid i is marked with an integer a[i], that means if you move into that grid, then you will immediately jump |a[i]| grids more ( if a[i] > 0, the direction is forward, otherwise it's backward ). For example, suppose grid 5 is marked with integer 3, -3 respectively, then when you come to grid 5, you will immediately move to grid 8 or 2 correspondingly. Of course, if a[i] is 0, then you will stay at grid i. It's guaranteed that you will always jump into a grid marked with 0.

What's worse, the sequence is cyclic, that means when you are moving to a grid k which is out of the range of 0 and n-1, you will actually move to grid k%n.

Now, given the configuration of the grids, please write a program to calculate the expected number of moves to reach grid n-1.

Input may contain several test cases. The first lines is a positive integer T, ( 1 ≤ T ≤ 20 ), the number of test cases below. Each test cases starts with a positive integer n, ( 1 ≤ n ≤ 100 ), the number of grids in the game, followed by n integers a[i] ( -n ≤ a[i] ≤ n ,  1 ≤ i ≤ n ). It's guaranteed that grid 0 and grid n-1 is always marked with 0.

For each test case, please output the expected number of moves to reach grid n-1, round to 3 digits after the decimal point. If it's impossible to reach grid n-1, simply output "-1".

2
3
0 0 0
8
0 -1 -2 -3 -4 -5 -6 0

3.000
-1