1367_E. 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):

<image>

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

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

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

Input

The first line contains a single integer t (1 ≤ t ≤ 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 ≤ n, k ≤ 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".
```python
from collections import Counter
from math import ceil, sqrt


class DisjSet:
    def __init__(self, n):
        # Constructor to create and
        # initialize sets of n items
        self.rank = [1] * n
        self.parent = [i for i in range(n)]
        self.extra = []

    # Finds set of given item x
    def find(self, x):

        # Finds the representative of the set
        # that x is an element of
        if (self.parent[x] != x):
            # if x is not the parent of itself
            # Then x is not the representative of
            # its set,
            self.parent[x] = self.find(self.parent[x])

        # so we recursively call Find on its parent
        # and move i's node directly under the
        # representative of this set

        return self.parent[x]

    # Do union of two sets represented
    # by x and y.
    def Union(self, x, y):

        # Find current sets of x and y
        xset = self.find(x)
        yset = self.find(y)

        # If they are already in same set
        if xset == yset:
            self.extra.append((x, y))
            return

        # Put smaller ranked item under
        # bigger ranked item if ranks are
        # different
        if self.rank[xset] < self.rank[yset]:
            self.parent[xset] = yset

        elif self.rank[xset] > self.rank[yset]:
            self.parent[yset] = xset

        # If ranks are same, then move y under
        # x (doesn't matter which one goes where)
        # and increment rank of x's tree
        else:
            self.parent[yset] = xset
            self.rank[xset] = self.rank[xset] + 1


t = int(input())


def get_factors(n):
    fact = []
    for i in range(1, int(ceil(sqrt(n))) + 1):
        if n % i == 0:
            fact.append(i)
            fact.append(n // i)
    return fact


for _ in range(t):
    n, k = list(map(int, input().split()))
    a = input()
    count = dict(Counter(a))
    count = sorted(count.items(), reverse=True, key=lambda x: x[1])

    maxi = 0
    for m in range(1, n+1):
        counts = [x[1] for x in count]
        obj = DisjSet(n)
        for i in range(0, m):
            obj.Union(i, (i + k) % m)
        hashmap = {}
        for i in range(0, m):
            x = obj.find(i)
            if x not in hashmap:
                hashmap[x] = 0
            hashmap[x] += 1
        hashmap = sorted(hashmap.items(), reverse=True, key=lambda x: x[1])
        # print(m,hashmap,counts)

        flag1=1
        for i in range(0, len(hashmap)):
            flag = 0
            for j in range(0, len(counts)):
                if counts[j] >= hashmap[i][1]:
                      counts[j]-=hashmap[i][1]
                      flag=1
                      break

            if flag==0:
                flag1=0
                break
        if flag1==1:
            maxi=m
    print(maxi)
```