Statement

Monocarp wants to throw a party. He has $n$ friends, and he wants to have at least $2$ of them at his party.

The $i$ -th friend's best friend is $p_i$ . All $p_i$ are distinct, and for every $i \in [1, n]$ , $p_i \ne i$ .

Monocarp can send invitations to friends. The $i$ -th friend comes to the party if both the $i$ -th friend and the $p_i$ -th friend receive an invitation (note that the $p_i$ -th friend doesn't have to actually come to the party). Each invitation is sent to exactly one of the friends.

For example, if $p = [3, 1, 2, 5, 4]$ , and Monocarp sends invitations to the friends $[1, 2, 4, 5]$ , then the friends $[2, 4, 5]$ will come to the party. The friend $1$ won't come since his best friend didn't receive an invitation; the friend $3$ won't come since he didn't receive an invitation.

Calculate the minimum number of invitations Monocarp has to send so that at least $2$ friends come to the party.

Format

Input

The first line contains one integer $t$ ( $1 \le t \le 5000$ ) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ( $2 \le n \le 50$ ) — the number of friends;
• the second line contains $n$ integers $p_1, p_2, \dots, p_n$ ( $1 \le p_i \le n$ ; $p_i \ne i$ ; all $p_i$ are distinct).

Output

Print one integer — the minimum number of invitations Monocarp has to send.

Sample

3
5
3 1 2 5 4
4
2 3 4 1
2
2 1

2
3
2