P13469 [GCJ 2008 #2] PermRLE

你发明了一种对游程编码（RLE）压缩算法的轻微修改，称为 PermRLE。 为了压缩一个字符串，该算法选择 $1$ 到 $k$ 之间整数的某个排列，将该排列应用到给定字符串的前 $k$ 个字母，然后应用到接下来的 $k$ 个字母的块，依此类推。字符串的长度必须能被 $k$ 整除。在对所有块进行排列后，新的字符串将使用 RLE 进行压缩，RLE 的描述见下文。 将给定的排列 $p$ 应用于一个 $k$ 个字母的块，意味着将这些字母中的第 $p[1]$ 个放在第一个位置，第 $p[2]$ 个放在第二个位置，依此类推。例如，将排列 $\{3,1,4,2\}$ 应用于块 "abcd"，得到 "cadb"。将其应用于更长的字符串 "abcdefghij" 的各个块，得到 "cadbgehfik"。 排列后的字符串随后使用游程编码进行压缩。为简化起见，我们将字符串的压缩大小定义为连续相同字母分组的数量。例如，"aabcaaaa" 的压缩大小为 $4$；四个分组分别是两个字母 "a" 的一组，然后 "b" 和 "c" 各自为一组，最后是一组较长的 "a"。 显然，压缩大小可能取决于所选择的排列。由于压缩算法的目标是最小化压缩文本的大小，你的任务是选择能得到最小压缩大小的排列，并输出该最小值。

第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 组测试用例。 每组测试用例的第一行包含一个整数 $k$。第二行包含要压缩的字符串 $S$。

对于每个测试用例，输出一行，格式为 "Case #X: Y"，其中 $X$ 是测试用例编号，$Y$ 是 $S$ 的最小压缩大小。

**限制条件** - $N = 20$ - $S$ 只包含小写字母 'a' 到 'z' - $S$ 的长度能被 $k$ 整除 **小数据范围（5 分，测试集 1 - 可见）** - $2 \leq k \leq 5$ - $1 \leq S$ 的长度 $\leq 1000$ **大数据范围（30 分，测试集 2 - 隐藏）** - $2 \leq k \leq 16$ - $1 \leq S$ 的长度 $\leq 50000$ 由 ChatGPT 4.1 翻译