你发明了一种对行程编码（RLE）压缩算法的微小改进，称为 PermRLE。

为了压缩一个字符串，该算法选择一个 $1$ 到 $k$ 之间的整数排列，将此排列应用于给定字符串的前 $k$ 个字母，然后应用于接下来的 $k$ 个字母，依此类推。字符串的长度必须能被 $k$ 整除。在对所有块进行置换后，新字符串使用行程编码（RLE）进行压缩，具体描述如下。

将给定的排列 $p$ 应用于一个长度为 $k$ 的字母块，意味着将这些字母中的第 $p[1]$ 个放在第一个位置，将第 $p[2]$ 个放在第二个位置，以此类推。例如，将排列 $\{3,1,4,2\}$ 应用于块 "abcd" 会得到 "cadb"。将其应用于更长的字符串 "abcdefghijkl" 时，分块处理会得到 "cadbgehfkilj"。

置换后的字符串随后使用行程编码进行压缩。为简化起见，我们将字符串的压缩大小定义为连续相同字母组的数量。例如，"aabcaaaa" 的压缩大小为 4；四个组中的第一个是两个字母 "a" 的组，然后是两个各包含一个字母的 "b" 和 "c" 组，最后是一个较长的 "a" 字母组。

显然，压缩大小取决于所选的排列。由于压缩算法的目标是最小化压缩文本的大小，你的任务是选择能产生最小压缩大小的排列，并输出该大小。

输入格式

输入的第一行包含测试用例的数量 $N$。接下来是 $N$ 个测试用例。

每个测试用例的第一行包含 $k$。第二行包含要压缩的字符串 $S$。

输出格式

对于每个测试用例，输出一行 "Case #$X$: $Y$"（引号仅为清晰起见），其中 $X$ 是测试用例的编号，$Y$ 是 $S$ 的最小压缩大小。

数据范围

$N = 20$

$S$ 仅包含小写字母 'a' 到 'z'

$S$ 的长度能被 $k$ 整除

小数据集（测试集 1 - 可见；5 分）

$2 \le k \le 5$

$1 \le \text{length of } S \le 1000$

大数据集（测试集 2 - 隐藏；30 分）

$2 \le k \le 16$

$1 \le \text{length of } S \le 50000$

样例

输入 1

2
4
abcabcabcabc
3
abcabcabcabc

输出 1

Case #1: 7
Case #2: 12