Necklace Assembly

题意翻译

一家商店出售 $n$ 颗珠子。每个珠子的颜色由英文小写字母表示。你想买一些珠子来组装一个项链。一个项链连成一圈的珠子。 例如，如果商店出售珠子 $a,b,c,a,c,c$ 那么您可以组装成下面的项链（非所有的方法）：  可是以下项链无法组装（非所有的方法）：  第一条项链无法组装，因为它有三个珠子 $a$，但是实际上只有两个。第二条项链无法组装，因为它含有一个没有出售的珠子 $d$。 如果一个项链按顺时针旋转 $k$ 圈时，项链始终保持不变，我们称项链是美丽的。例如，下面是一个项链的旋转过程：  您将获得整数 $n$ 和 $k$，还有 $n$ 个小写字母的字符串，每个字母表示出售的一个珠子。你可以使用任何一个珠子，并且可以用任何顺序来连接它们，使得他们成为一个项链。求你可以最大可以组装的美丽的长度。 由 $殲谶灬巭$ 翻译

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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".