Richard is a travel freak. He is now out to travel to a distant place with his friends, so he took his car and went out with a certain amount of fuel. Thus he must stop at a fuel station before his fuel gets over. There are several fuel station with 1 km gap providing fixed amount of fuel.

At each fuel station his tank is first emptied and then refueled by the amount of fuel that the current fuel station provides.

Help him reach his destination as fast as possible making minimum no of stops as there is a party planned at his destination.

INPUT

First Line contains no of test cases T.

For Each Test case,

First line contains an integer D, (distance to his destination + 1).

Next line contains D space-separated integers (N) which is the amount of fuel a fuel station at that kilometer provides. The first digit in this line shows the amount of Fuel he started with.

Output

T lines of Integers showing the minimum no of stops he can make to reach the destination for each test case.

Constraints

T ≤ 10000

1 ≤ D ≤ 100000

1 ≤ N ≤ 1000

Note:
He can go 1km with 1 Litre of Petrol.

SAMPLE INPUT
2
5
2 15 5 6 2
11
1 3 5 8 9 2 6 7 6 8 9

SAMPLE OUTPUT
1
2

Explanation

First Test case contains 5 Integers.

Initially he has 2 litres of fuel, so he can go up to 2Kms. Thus he makes a stop at 1st Km. There he gets 15 Liters of fuel by which he can reach the end of his destination So only one stop needed.

For the second test case, which contain 11 integers.

He Starts with 1 Litre of Fuel, Stops at 1st Km refueling 3 Litres of fuel. Then he stops at the 4th Km filling 9 litres by which he can reach his destination. Thus two stops needed.

Note: For updated Problem Statement

1

5

4 1 9 1 4

for this input output must be

0

since he hast 4 litres of fuel and can reach to the destination by itself.

见题面

见题面