CF1367E.Necklace Assembly

The store sells $n$ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.

A necklace is a set of beads connected in a circle.

For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options):

And the following necklaces cannot be assembled from beads sold in the store:

The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store.

We call a necklace $k$-beautiful if, when it is turned clockwise by $k$ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.

As you can see, this necklace is, for example, $3$-beautiful, $6$-beautiful, $9$-beautiful, and so on, but it is not $1$-beautiful or $2$-beautiful.

In particular, a necklace of length $1$ is $k$-beautiful for any integer $k$. A necklace that consists of beads of the same color is also beautiful for any $k$.

You are given the integers $n$ and $k$, and also the string $s$ containing $n$ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $k$-beautiful necklace you can assemble.

商店出售 $n$ 颗珠子。每颗珠子的颜色由一个英文字母小写字符（"a"–"z"）表示。你想购买若干颗珠子，用它们串成一条项链。

项链是一组首尾相连、构成环形的珠子。

例如，若商店出售的珠子为 "a"、"b"、"c"、"a"、"c"、"c"，则你可以用它们组成如下项链（这些并非全部可能的组合）：

而以下项链则无法用商店所售珠子组装而成：

第一条项链无法组装，是因为它需要三颗 "a" 珠子，而商店中仅有两颗；第二条项链无法组装，是因为它含有一颗商店未售出的 "d" 珠子。

我们称一条项链是 $k$-优美的（$k$-beautiful），当且仅当将其顺时针旋转 $k$ 颗珠子后，项链外观保持不变。例如，下图展示了一条项链连续三次旋转的过程：

如图所示，该项链例如是 $3$-优美、$6$-优美、$9$-优美等，但不是 $1$-优美或 $2$-优美。

特别地，长度为 $1$ 的项链对任意整数 $k$ 均为 $k$-优美；全部由同色珠子组成的项链也对任意 $k$ 均为 $k$-优美。

现给你整数 $n$ 和 $k$，以及一个长度为 $n$ 的字符串 $s$，其中每个字符均为英文字母小写，代表商店中一颗珠子的颜色。你可以购买任意子集的珠子，并以任意顺序将它们连接成环。请找出你能组装出的最长的 $k$-优美项链的长度。

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2000$).

The second line of each test case contains the string $s$ containing $n$ lowercase English letters — the beads in the store.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$.

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2000$）。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成——表示商店中的珠子。

保证所有测试用例的 $n$ 值之和不超过 $2000$。

Output $t$ answers to the test cases. Each answer is a positive integer — the maximum length of the $k$-beautiful necklace you can assemble.

输出 $t$ 个测试用例的答案。每个答案均为一个正整数——你能组装出的 $k$-beautiful 项链的最大长度。

The first test case is explained in the statement.

In the second test case, a $6$-beautiful necklace can be assembled from all the letters.

In the third test case, a $1000$-beautiful necklace can be assembled, for example, from beads "abzyo".

第一个测试用例已在题目描述中说明。

在第二个测试用例中，可以使用所有字母组装出一条 $6$-美丽的项链。

在第三个测试用例中，例如可以使用珠子 "abzyo" 组装出一条 $1000$-美丽的项链。