편지 돌리기

Albert와 친구들은 편지 릴레이 놀이를 즐겨한다. 총 $N$명의 어린이가 1번부터 $N$번까지 번호를 달고 있고, 각자 편지를 한 장씩 쓴다. 편지지에는 편지를 쓴 아이 자신의 번호를 적는다. 모두 편지를 쓴 뒤, $i$번째 아이는 자신이 쓴 편지를 $F_i$번째 아이에게 전달한다. $F_i = i$인 경우에는 자신의 편지를 자신이 갖고 있으면 된다. 공평한 놀이가 되려면 모든 아이가 반드시 한 장씩 받아야 한다. 따라서 배열 $F$에는 $1$부터 $N$까지의 정수가 정확히 한 번씩 등장한다. 편지 전달 방법을 나타내는 배열 $F$를 "편지 돌리기 배열"이라 부르자. $N$명의 아이가 모두 동시에 규칙대로 다음 아이에게 편지를 넘기면 편지를 "한 번" 돌린 것이다. 이를 반복하면 언젠가 각자 처음에 쓴 편지를 받게 된다.

$k$번 편지를 돌린 뒤 $i$번째 아이가 갖고 있는 편지에 쓰인 번호를 $L_F(k, i)$라 하자.

• $k = 0$: 편지를 돌리기 전에는 모든 아이가 자신이 쓴 편지를 갖고 있다.
• $k = 1$: 한 번 돌린 뒤 1번 아이는 자신의 편지를 2번 아이에게 주었으므로 2번 아이는 1번이 적힌 편지를 갖고 있다. 8번과 9번 아이는 서로 편지를 주고받았고, 10번 아이는 자신의 편지를 그대로 갖고 있다.
• $k = 2$: 1번부터 7번 아이는 자신의 편지를 갖고 있지 않지만, 8번, 9번, 10번 아이는 두 번째 돌리기가 끝난 뒤 각자 자신의 편지를 갖고 있다.
• $k = 3$: 1번, 2번, 3번, 10번 아이는 각자 자신의 편지를 갖고 있고, 나머지 아이들은 다른 아이가 쓴 편지를 갖고 있다.

Albert와 아이들은 최소 몇 번 돌려야 각자 자신의 편지를 손에 쥐게 되는지 쉽게 구할 수 있었다. 이를 $R(F)$라 쓰기로 했다. 수학적으로는 모든 $1 \le i \le N$에 대해 $L_F(k, i) = i$를 만족하는 가장 작은 $k > 0$이다. 이 값을 $F$의 "편지 돌리기 점수"라 하자. 위 예제에서 $F$의 편지 돌리기 점수는 12이다.

새로운 문제 만들기를 좋아하는 Albert는 이보다 조금 더 어려운 문제를 생각해 냈다. 먼저 임의의 두 정수 $1 \le x, y \le N$을 고른다. 그다음 $F_x$와 $F_y$의 값을 맞바꾸면 새로운 편지 돌리기 배열 $G_{F, x, y}$를 얻을 수 있다. $F$의 나머지 원소는 바꾸지 않는다. $x = y$인 두 정수를 고르면 당연히 $G_{F, x, y} = F$이고, 이것도 허용한다. 이렇게 얻을 수 있는 모든 배열 $G_{F, x, y}$의 편지 돌리기 점수 중 최솟값을 구해 보고 싶다.

위의 예제에서 $x = 1$, $y = 10$을 고르면 $G_{F, x, y} = [10, 3, 1, 5, 6, 7, 4, 9, 8, 2]$가 된다. 이때 네 번 돌린 뒤 각 아이가 들고 있는 편지의 번호는 아래 그림과 같고, 이 배열의 편지 돌리기 점수는 4점이다.

이 예제에서 $F$ 배열의 두 원소 값을 교환하여 얻을 수 있는 편지 돌리기 점수의 최솟값은 4점이다.

입력으로 $N$과 $F$가 주어졌을 때, $F$의 편지 돌리기 점수와 $F$의 두 원소 값을 교환하여 얻을 수 있는 편지 돌리기 점수의 최솟값을 구하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 둘째 줄에는 배열 $F$의 원소 $N$개가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답인 두 정수를 공백으로 구분하여 한 줄에 출력한다. 첫 번째 정수는 $F$의 편지 돌리기 점수이고, 두 번째 정수는 $F$의 원소 두 개를 교환하여 새 배열을 만들었을 때 얻을 수 있는 편지 돌리기 점수의 최솟값이다.

• $1 \le T \le 10$
• $2 \le N \le 250000$
• $1 \le i \le N$인 모든 $i$에 대하여 $1 \le F_i \le N$이다.
• 배열 $F$의 원소는 고유하다(중복된 값이 주어지지 않는다).
• 각 테스트 케이스의 정답인 두 정수 값이 모두 $10^{13}$ 이하인 입력만 주어진다.