write a c program where You live on a street with N houses. The houses are labelled as 1 2 . . . N, from left to right. You live in the house labelled 1, i.e the left-most house. and you wish to reach the house labelled N i.e. the right-most house.

There is a tunnel present in each house. The tunnel present in the house labelled ii can be used to reach any house labelled j, such that jiAi

Determine the minimum number of houses you can visit in order to reach the right-most house. Input Format

First line will contain T, number of testcases. Then the testcases follow. The first line of each testcase contains a single integer N. The second line of each testcase contains N integers : A1,A2...AN.

It is guaranteed that the sum of the values of N over all the test cases doesn't exceed 310^6. Output Format

For each testcase, output in a single integer equal to the minimum number of houses you can visit in order to reach the right-most house. Constraints

1T50 1N10^5 1Ai10^5

Test-case 1: You use the tunnel present in the house labelled 11 to reach the house labelled 33. Thus, you visited 22 houses in total, the house labelled 11 and the house labelled 33.

Test-case 2: One of the ways to reach the house labelled NN is to

Use the tunnel in house labelled 11 to reach house labelled 22.

Use the tunnel in house labelled 22 to reach house labelled 66.

Use the tunnel in house labelled 66 to reach house labelled 88.

Thus we visit 44 houses in total. There exists no way to reach house labelled NN by visiting less than 44 houses.

INPUT : (JUST A EXAMPLE)

2

3

2 1 1

8

3 4 2 1 1 2 1 8

OUTPUT :

2

4