PermRLE (Small)

You have written a small variation of run-length encoding (RLE) called PermRLE.

To compress a string, this algorithm picks a permutation of the integers from 1 to $k$, applies that permutation to the first $k$ letters of the string, then to the next block of $k$ letters, and so on to the last block. The length of the string must be divisible by $k$. After every block is rearranged, the new string is compressed with the RLE described below.

Applying a permutation $p$ to a block of $k$ letters means placing the $p[1]$-th letter of that block in the first position, the $p[2]$-th letter in the second position, and so on up to the $k$-th position. For example, applying the permutation $\{3, 1, 4, 2\}$ to the block abcd gives cadb. Applying the same permutation block by block to the longer string abcdefghijkl gives cadbgehfkilj.

The rearranged string is then compressed with run-length encoding. To keep things simple, the compressed size of a string is the number of groups of consecutive equal letters. For example, the compressed size of aabcaaaa is 4. The first of the four groups holds two copies of a, the next two groups hold a single b and a single c, and the last is a longer group of four copies of a.

The compressed size depends on the permutation you pick. Since a compression algorithm aims to make the compressed text as small as possible, pick the permutation that gives the smallest compressed size and print that size.

The first line of input gives the number of test cases, $N$. $N$ test cases follow.

The first line of each test case contains $k$. The second line contains $S$, the string to be compressed.

Limits

• $1 \le N \le 20$
• $S$ contains only the lowercase letters a through z.
• The length of $S$ is divisible by $k$.
• $2 \le k \le 5$
• $1 \le |S| \le 1000$

For each test case, print one line in the form Case #X: Y, where $X$ is the number of the test case and $Y$ is the minimum compressed size of $S$.