商店出售 $$$n$$$ 珠子。每个珠子的颜色由英文字母中的小写字母(“a”–“z”)描述。您想购买一些珠子来组装一条项链。
项链是一组连接成圆圈的珠子。
例如,如果商店出售珠子“a”、“b”、“c”、“a”、“c”、“c”,那么您可以组装以下项链(这些并非所有可能的选项):
以下项链不能由商店出售的珠子组装而成:
第一条项链无法组装,因为它有三个珠子“a”(两个可用珠子中的一个)。第二条项链无法组装,因为它包含一颗珠子“d”,该珠子不在商店中出售。
如果当 $$$k$$$ 珠子顺时针转动项链时,项链保持不变,则我们称其为 $$$k$$$-美丽。例如,这是一条项链的三圈序列。
特别是,一条长度为 $$$1$$$ 的项链对于任何整数 $$$k$$$ 都是美丽的 $$$k$$$。对于任何 $$$k$$$ 来说,由相同颜色的珠子组成的项链也很漂亮。
您将获得整数 $$$n$$$ 和 $$$k$$$,以及包含 $$$n$$$ 英文字母小写字母的字符串 $$$s$$$ — 每个字母定义商店中的一个珠子。您可以购买任何珠子子集并以任何顺序连接它们。找出您可以组装的 $$$k$$$ 漂亮项链的最大长度。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试中的测试用例数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2000$$$)。
每个测试用例的第二行包含字符串 $$$s$$$,其中包含 $$$n$$$ 小写英文字母 - 商店中的珠子。
保证所有测试用例的$$$n$$$总和不超过$$$2000$$$。
输出
输出测试用例的 $$$t$$$ 答案。每个答案都是一个正整数——您可以组装的 $$$k$$$ 美丽项链的最大长度。
示例
输入 #1
6 6 3 abcbac 3 6 aaa 7 1000 abczgyo 5 4 ababa 20 10 aaebdbabdbbddaadaadc 20 5 ecbedececacbcbccbdec
输出 #1
6 3 5 4 15 10
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,可以用所有字母组装一条 $$$6$$$ 漂亮的项链。
在第三个测试用例中,可以用珠子“abzyo”组装一条 $$$1000$$$ 的漂亮项链。