The Game of Death

Interview

Time limit1sMemory limit256 MB

Summary

Starting from player 1, follow the pointed-to players and report the first step that reaches player N, or 0 when it never does.

Level: Easy3 of 10
Topics: Graph, Simulation
Solved: No attempts yet

Problem

Heehyun and Jookyung like the game of death.

The rules are these.

Every player points at exactly one player. Pointing at yourself is allowed.
The player who starts the game says a positive integer $K$ .
The player that the starter points at is the first player pointed at, the player that this player points at is the second one, and so on. The $K$ -th player pointed at loses.

Heehyun starts the game and wants Jookyung to lose. Find the number Heehyun has to say.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 100$ ).

The first line of each test case has the number of players $N$ ( $1 \le N \le 10000$ ). Each of the next $N$ lines has one integer, the $i$ -th of them being $A_i$ ( $1 \le A_i \le N$ ), the player that player $i$ points at.

Heehyun is player 1 and Jookyung is player $N$ . When $N$ is 1, Heehyun and Jookyung are the same person.

Output

For each test case, print on one line the smallest $K$ that makes Jookyung lose.

If no number makes Jookyung lose, print 0.

Examples7

Example 1
Input
```
1
7
2
3
4
5
6
7
1
```
Expected output
```
6
```
Example 2
Input
```
1
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
2
1
1
```
Expected output
```
0
```
Example 4
Input
```
1
2
2
1
```
Expected output
```
1
```
Example 5
Input
```
1
4
3
1
4
4
```
Expected output
```
2
```
Example 6
Input
```
1
5
2
3
4
3
1
```
Expected output
```
0
```

Example 7

Input

Expected output

0
4
0