Mod-3 Permutation

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 permutation in the minimum number of steps. For each step of the conversion, you need to select two different indices and swap their values.

INPUT

- 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.

OUTPUT

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.

Sample Input

Sample Output

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