Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Necklace Assembly

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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:

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

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

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

Example

Input

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

Output

6 3 5 4 15 10

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/28/2021 16:55:13 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|