CF1367E Necklace Assembly

商店出售 $n$ 颗珠子。每颗珠子的颜色由一个小写英文字母（“a”–“z”）表示。你想购买一些珠子，用它们组装成一条项链。 项链是一组首尾相连成环的珠子。 例如，如果商店出售的珠子为 “a”、 “b”、 “c”、 “a”、 “c”、 “c”，那么你可以组装出如下项链（这并不是所有可能的选项）：  而下面这些项链无法用商店出售的珠子组装出来：  第一个项链无法组装，是因为它包含了三个 “a” 珠子，而商店只有两个。第二个项链无法组装，是因为它包含了一个商店没有出售的 “d” 珠子。 我们称一条项链是 $k$-美丽的，如果将它顺时针旋转 $k$ 个珠子后，项链保持不变。例如，下面是对一条项链顺时针旋转三次的示意图。  如你所见，这条项链是 $3$-美丽的、$6$-美丽的、$9$-美丽的，等等，但不是 $1$-美丽的或 $2$-美丽的。 特别地，长度为 $1$ 的项链对于任意整数 $k$ 都是 $k$-美丽的。由同色珠子组成的项链对于任意 $k$ 也都是美丽的。 现在给定整数 $n$ 和 $k$，以及一个包含 $n$ 个小写英文字母的字符串 $s$，每个字母表示商店中的一颗珠子。你可以购买任意子集的珠子，并以任意顺序连接它们。请你求出你能组装出的 $k$-美丽项链的最大长度。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2000$）。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成，表示商店中的珠子。 保证所有测试用例中 $n$ 的总和不超过 $2000$。

输出 $t$ 行，每行一个正整数，表示每个测试用例中你能组装出的 $k$-美丽项链的最大长度。

第一个测试用例的解释见题面。 在第二个测试用例中，可以用所有字母组装出一个 $6$-美丽的项链。 在第三个测试用例中，可以用 “abzyo” 这五颗珠子组装出一个 $1000$-美丽的项链。 由 ChatGPT 4.1 翻译