레벨 설계

순열 $C$에서 순열 사이클이란 다음 조건을 만족하는 정수의 수열 $(a_1, a_2, \dots, a_k)$이다.

• 모든 $i$에 대해 $a_i \in C$이며, 이들은 서로 다르다.

• 각 $i \in \{1, 2, \ldots, k-1\}$에 대해 $C[a_i] = a_{i+1}$이고, $C[a_k] = a_1$이다.

길이가 $k$인 순열 사이클을 $k$-사이클이라고 한다.

예를 들어, 순열 $C = [4, 2, 1, 3]$에는 두 개의 사이클, 즉 $3$-사이클 $(4, 3, 1)$과 $1$-사이클 $(2)$이 있다. $(4, 3, 1)$는 $C[4] = 3$, $C[3] = 1$, 그리고 $C[1] = 4$이므로 사이클이다.

Grace는 순열 사이클을 매우 좋아하므로, Charles는 그녀에게 도전 과제를 주기 위해 $\mathbf{N}$개 레벨로 이루어진 게임을 설계하기로 한다.

게임이 시작될 때 플레이어에게 $1$부터 $\mathbf{N}$까지의 정수로 이루어진 길이 $\mathbf{N}$의 순열 $\mathbf{P}$가 주어진다. 게임의 레벨에는 $1$부터 $\mathbf{N}$까지 번호가 매겨져 있다. 각 레벨에서 플레이어는 주어진 순열로 시작하며, 그 안의 임의의 두 원소를 서로 바꾸어 순열을 변경할 수 있다(여러 번 교환할 수 있다). 게임의 $k$번째 레벨을 완료하려면 플레이어는 순열에 $k$-사이클을 만들 수 있는 최소 교환 횟수를 구해야 한다. 플레이어는 $k$번째 레벨을 완료한 후에만 $(k+1)$번째 레벨로 진행할 수 있다.

Grace는 게임이 다소 어렵다고 생각하지만, 어떤 대가를 치르더라도 이기고 싶어 한다. 그녀에게는 여러분의 도움이 필요하다! 형식적으로, 각 레벨 $k$에 대해 순열에 $k$-사이클을 만들 수 있는 최소 교환 횟수를 구해야 한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{P_i} \le \mathbf{N}$. 모든 $\mathbf{P_i}$는 서로 다르다.

테스트 세트 1

$1 \le \mathbf{N} \le 10^3$.

테스트 세트 2

$1 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 순열의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다. 다음 줄에는 $\mathbf{N}$개의 정수 $\mathbf{P_1}$, $\mathbf{P_2}$, $\dots$, $\mathbf{P_N}$가 주어지며, $i$번째 정수는 순열 $\mathbf{P}$의 $i$번째 원소를 나타낸다.

각 테스트 케이스마다 Case #$x$: $S_1, S_2, \dots, S_N$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 (1부터 시작), $S_i$는 게임의 $i$번째 레벨에 대한 답, 즉 순열에 $i$-사이클을 만드는 데 필요한 최소 교환 횟수이다.

예제 케이스 #1에서 주어진 순열에는 $1$-사이클이 세 개 있다. 따라서 첫 번째 레벨은 교환 없이 완료할 수 있다. 두 번째 레벨을 완료하려면 처음 두 원소를 서로 바꾸어 순열 $[2, 1, 3]$을 얻을 수 있으며, 이 순열에는 $2$-사이클 $(2, 1)$이 포함되어 있다. 세 번째 레벨을 완료하려면 처음 두 원소를 서로 바꾼 다음 둘째 원소와 셋째 원소를 서로 바꾸어 순열 $[2, 3, 1]$을 얻을 수 있으며, 이 순열에는 $3$-사이클 $(2, 3, 1)$가 포함되어 있다.

예제 케이스 #2에서 앞서 설명했듯이 순열에는 $1$-사이클 $(2)$가 있다. 따라서 첫 번째 레벨을 완료하는 데 교환이 필요하지 않다. 두 번째 레벨을 완료하려면 마지막 두 원소를 서로 바꾸어 순열 $[4, 2, 3, 1]$을 얻을 수 있으며, 이 순열에는 $2$-사이클 $(4, 1)$가 포함되어 있다. 이 순열에는 $3$-사이클 $(4, 3, 1)$도 있으므로 세 번째 레벨 역시 교환 없이 완료할 수 있다. 네 번째 레벨을 완료하려면 둘째 원소와 넷째 원소를 서로 바꾸어 순열 $[4, 3, 1, 2]$을 얻을 수 있으며, 이 순열에는 $4$-사이클 $(4, 2, 3, 1)$가 포함되어 있다.