시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

We call a permutation p0, p1, ... , pn-1 of a sequence of integers 0, 1, ... , n-1 mod-3 when for each index i, pi mod 3 = i mod 3. For example, the permutation 3,1,5,0,4,2 is mod-3 but the permutation 1,2,0,4,5,3 is not. You will be given a permutation. You are required to convert the given permutation into a mod-3 permutationin the minimum number of steps. For each step of the conversion, you need to select two different indices and swap their values. 

입력

The first line has a positive integer T, T <= 100000, denoting the number of test cases. This is followed by each test case per line.

Each test case consists of two lines; the first line contains an integer n while the next line contains n integers separated by a single space. These n integers denotes a permutation of 0, 1, .., n-1. n is between 3 and 501 inclusive and is always a multiple of 3. 

출력

For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the minimum number of swaps required to convert the given permutation into a mod-3 permutation. 

예제 입력

10
3
2 0 1
6
1 0 3 2 5 4
6
4 0 3 5 2 4
6
5 3 4 2 0 1
3
0 2 1
9
5 3 8 6 7 0 1 2 4
9
2 1 7 3 5 4 8 6 0
9
3 5 2 0 6 4 7 1 8
9
5 7 1 8 2 6 0 4 3
9
8 3 5 0 6 7 4 2 1

예제 출력

Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 4
Case #5: 1
Case #6: 3
Case #7: 4
Case #8: 2
Case #9: 3
Case #10: 4

힌트