$$$n$$$ 人们来到节日并决定跳几段圆舞。圆舞会中至少有 $$$2$$$ 人,并且每个人恰好有两个邻居。如果圆舞中有 $$$2$$$ 人,那么他们每一边都有同一个邻居。
您决定找出到底有多少支舞蹈。但假期的每个参与者都准确地记得一个邻居。您的任务是确定圆舞的最小和最大数量。
例如,如果节日有 $$$6$$$ 人,并且他们记住的邻居数量等于 $$$[2, 1, 4, 3, 6, 5]$$$,则圆舞的最少数量为 $$$1$$$:
- $$$1 - 2 - 3 - 4 - 5 - 6 - 1$$$
- $$$1 - 2 - 1$$$
- $$$3 - 4 - 3$$$
- $$$5 - 6 - 5$$$
输入
第一行包含一个正数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。以下是测试用例的描述。
每个测试用例描述的第一行包含一个正数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 假期的人数。
每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le n, a_i \neq i$$$) — 第 $$$i$$$ 人记住的邻居的号码。
保证测试用例正确,并且对应至少一组人进行圆舞。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个整数——可能的最小和最大圆舞数量。
示例
输入 #1
10 6 2 1 4 3 6 5 6 2 3 1 5 6 4 9 2 3 2 5 6 5 8 9 8 2 2 1 4 4 3 2 1 5 2 3 4 5 1 6 5 3 4 1 1 2 5 3 5 4 1 2 6 6 3 2 5 4 3 6 5 1 4 3 4 2
输出 #1
1 3 2 2 1 3 1 1 1 2 1 1 1 1 2 2 1 2 1 1