Mod-3 순열

정수 $0, 1, \dots, n-1$을 한 번씩 나열한 순열 $p_0, p_1, \dots, p_{n-1}$이 모든 인덱스 $i$에서 $p_i \bmod 3 = i \bmod 3$을 만족하면, 이 순열을 mod-3 순열이라고 한다. 예를 들어 3, 1, 5, 0, 4, 2는 mod-3 순열이지만 1, 2, 0, 4, 5, 3은 mod-3 순열이 아니다.

순열이 하나 주어진다. 한 번의 연산에서 서로 다른 두 인덱스를 골라 그 두 위치의 값을 교환할 수 있다. 주어진 순열을 mod-3 순열로 바꾸는 데 필요한 최소 연산 횟수를 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $1 \le T \le 100000$이다.

각 테스트 케이스는 두 줄이다. 첫째 줄에 정수 $n$이 주어지고, 둘째 줄에 공백 하나로 구분된 $n$개의 정수가 주어진다. 이 $n$개의 정수는 $0, 1, \dots, n-1$의 순열이다. $n$은 $3 \le n \le 501$을 만족하며 항상 3의 배수다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, M은 주어진 순열을 mod-3 순열로 바꾸는 데 필요한 최소 교환 횟수다.