311309: CF1969A. Two Friends

A. Two Friendstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

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.

ExampleInput

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

Output

2
3
2

Note

In the first testcase, Monocarp can send invitations to friends $4$ and $5$. Both of them will come to the party since they are each other's best friends, and both of them have invitations.

In the second testcase, Monocarp can send invitations to friends $1, 2$ and $3$, for example. Then friends $1$ and $2$ will attend: friend $1$ and his best friend $2$ have invitations, friend $2$ and his best friend $3$ have invitations. Friend $3$ won't attend since his friend $4$ doesn't have an invitation. It's impossible to send invitations to fewer than $3$ friends in such a way that at least $2$ come.

In the third testcase, Monocarp can send invitations to both friends $1$ and $2$, and both of them will attend.

题目大意：
单角鹿想举办一个派对，他有n个朋友，希望至少有2个朋友能来。每个朋友的最好朋友是p_i，所有p_i都是不同的，并且对于每个i属于[1, n]，p_i不等于i。单角鹿可以发送邀请给朋友，第i个朋友会来派对如果第i个朋友和第p_i个朋友都收到邀请（注意第p_i个朋友不必真的来派对）。每个邀请都是发送给一个朋友。

计算单角鹿至少需要发送多少邀请，以便至少有2个朋友来派对。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤5000）——测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数n（2≤n≤50）——朋友的数量；
- 第二行包含n个整数p_1, p_2, …, p_n（1≤p_i≤n；p_i不等于i；所有p_i都是不同的）。

输出：
- 打印一个整数——单角鹿至少需要发送的邀请数量。

示例：
输入：
3
5
3 1 2 5 4
4
2 3 4 1
2
2 1

输出：
2
3
2

注意：
- 在第一个测试用例中，单角鹿可以邀请朋友4和朋友5。他们都会来派对，因为他们是彼此最好的朋友，并且都收到了邀请。
- 在第二个测试用例中，单角鹿可以邀请朋友1、2和3，例如。然后朋友1和朋友2会参加：朋友1和他的最好朋友2都有邀请，朋友2和他的最好朋友3都有邀请。朋友3不会参加，因为他的朋友4没有邀请。无法以少于3个朋友的方式发送邀请，以便至少有2个朋友来。
- 在第三个测试用例中，单角鹿可以邀请朋友1和朋友2，并且他们都会参加。题目大意： 单角鹿想举办一个派对，他有n个朋友，希望至少有2个朋友能来。每个朋友的最好朋友是p_i，所有p_i都是不同的，并且对于每个i属于[1, n]，p_i不等于i。单角鹿可以发送邀请给朋友，第i个朋友会来派对如果第i个朋友和第p_i个朋友都收到邀请（注意第p_i个朋友不必真的来派对）。每个邀请都是发送给一个朋友。 计算单角鹿至少需要发送多少邀请，以便至少有2个朋友来派对。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤5000）——测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数n（2≤n≤50）——朋友的数量； - 第二行包含n个整数p_1, p_2, …, p_n（1≤p_i≤n；p_i不等于i；所有p_i都是不同的）。 输出： - 打印一个整数——单角鹿至少需要发送的邀请数量。 示例： 输入： 3 5 3 1 2 5 4 4 2 3 4 1 2 2 1 输出： 2 3 2 注意： - 在第一个测试用例中，单角鹿可以邀请朋友4和朋友5。他们都会来派对，因为他们是彼此最好的朋友，并且都收到了邀请。 - 在第二个测试用例中，单角鹿可以邀请朋友1、2和3，例如。然后朋友1和朋友2会参加：朋友1和他的最好朋友2都有邀请，朋友2和他的最好朋友3都有邀请。朋友3不会参加，因为他的朋友4没有邀请。无法以少于3个朋友的方式发送邀请，以便至少有2个朋友来。 - 在第三个测试用例中，单角鹿可以邀请朋友1和朋友2，并且他们都会参加。