Mod-3 Permutation

A permutation $p_0, p_1, \dots, p_{n-1}$ of the integers $0, 1, \dots, n-1$ is called mod-3 when $p_i \bmod 3 = i \bmod 3$ holds for every index $i$. For example, 3, 1, 5, 0, 4, 2 is a mod-3 permutation, while 1, 2, 0, 4, 5, 3 is not.

You are given one permutation. In a single step you can pick two different indices and swap the values at those two positions. Find the minimum number of steps that turns the given permutation into a mod-3 permutation.

The first line contains the number of test cases $T$, where $1 \le T \le 100000$.

Each test case takes two lines. The first line contains an integer $n$, and the second line contains $n$ integers separated by single spaces. Those $n$ integers are a permutation of $0, 1, \dots, n-1$. $n$ satisfies $3 \le n \le 501$ and is always a multiple of 3.

For each test case, print one line in the form Case #x: M, where x is the test case number starting from 1 and M is the minimum number of swaps that turns the given permutation into a mod-3 permutation.