Necklace Assembly
Contest: Codeforces Round 650 (Div. 3)
Difficulty rating: 1900
Tags: brute force, dfs and similar, dp, graphs, greedy, number theory

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.

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.

Input format:
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 format:
Output $$$t$$$ answers to the test cases. Each answer is a positive integer — the maximum length of the $$$k$$$-beautiful necklace you can assemble.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec

Example output:
6
3
5
4
15
10

Editorial:
Let's iterate over the $$$m$$$ — length of the $$$k$$$-beautiful necklace. For each position $$$i$$$, make an edge to the position $$$p[i] = (i + k) \bmod m$$$, where $$$a \bmod b$$$ — is the remainder of dividing $$$a$$$ by $$$b$$$. What is a cyclic shift by $$$k$$$ in this construction? A bead located at position $$$i$$$ will go along the edge to position $$$p[i]$$$. Consider all the cycles of a graph constructed on $$$p$$$. You may notice that if only equal letters are found in each cycle, then with a cyclic shift by $$$k$$$ the graph and the string will remain unchanged. Thus, in order to check whether it is possible to make a $$$k$$$-beautiful necklace of length $$$m$$$, you need to make a graph $$$p$$$, find the cycles in it and check whether it is possible to distribute the letters from the string $$$s$$$ in cycles such that each cycle have equal letters. The last part of the solution can be done with simple greedy.