PermRLE (Large)

You have built a slightly modified run-length encoding (RLE) compression algorithm called PermRLE.

To compress a string, the algorithm first picks a permutation of the integers from 1 to $k$. It applies that permutation to the first $k$ letters of the string, then to the next block of $k$ letters, and so on to the end of the string. The length of the string is divisible by $k$. After every block is permuted, the new string is compressed with RLE.

Applying a permutation $p$ to a block of $k$ letters means putting the $p[1]$-th letter of the 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 permuted string is then compressed with run-length encoding. Here the compressed size is the number of runs of consecutive equal letters. For example, the compressed size of "aabcaaaa" is 4. It splits into a run of two letters 'a', a run holding one 'b', a run holding one 'c', and finally a run of four letters 'a'.

The compressed size depends on the permutation you pick. Choose the permutation that makes the compressed size as small as possible and print that size.

The first line contains the number of test cases $N$. $N$ test cases follow.

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

Limits

• $1 \le N \le 20$
• $S$ contains only lowercase letters 'a' through 'z'
• The length of $S$ is divisible by $k$
• $2 \le k \le 16$
• $1 \le |S| \le 50000$

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