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

Difficulty: introductory

Starter code:

Solutions:
t = int(input())
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
for _ in range(t):
    n,k = map(int,input().split())
    s = input()
    occ = [0] * 26
    for i in s:
        occ[ord(i)-97] += 1
    occ.sort()
    occ.reverse()
    for l in range(1,n+1):
        cycle = gcd(l,k)
        need = l//cycle
        su = 0
        for i in occ:
            su += i//need
        if su*need >= l:
            wyn = l
    print(wyn)

import sys
input = sys.stdin.readline
from math import gcd

t=int(input())
for tests in range(t):
    n,k=list(map(int,input().split()))
    S=input().strip()

    LIST=[0]*26
    for s in S:
        LIST[ord(s)-97]+=1

    for x in range(n,0,-1):
        GCD=gcd(x,k)
        p=x//GCD

        SUM=0
        for l in LIST:
            if l>=p:
                SUM+=l//p*p

        if SUM>=x:
            print(x)
            break

    #print(S)
            

        
        


from math import *

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

def r3(t):
    return [t(i) for i in input()]

for _ in range(r1(int)):
    n, k = r2(int)
    s = r1(str)
    mp = {}
    for i in s:
        mp[i] = 0
    for i in s:
        mp[i] += 1

    t = sorted(list(mp.values()), reverse=True)
    ans = 1
    for x in range(1, k + 1):
        if k % x == 0:
            y = 1
            while True:
                ta = 0
                for i in t:
                    ta += i // y
                if (ta < x):    
                    break
                ans = max(ans, y*x)
                y += 1
 
    print(ans)


import math
t = int(input())
for _ in range(t):
    n,k = list(map(int,input().split()))
    s = input()
    countLetters = [0] * 26
    for elem in s:
        countLetters[ord(elem) - ord('a')] += 1
    factors = []
    for i in range(1,int(math.sqrt(k)) + 1):
        if k % i == 0:
            factors.append(i)
            factors.append(k//i)
    groups = []
    for i in range(1,n+1):
        sumBeads = 0
        for elem in countLetters:
            sumBeads += elem // i
        groups.append(sumBeads)
    maxNecklace = 0
    for elem in factors:
        maxGroup = 0
        for i in range(n):
            if groups[i] < elem:
                break
            else:
                maxGroup = i + 1
        if maxNecklace < maxGroup * elem:
            maxNecklace = maxGroup * elem
    print(maxNecklace)





def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)



t = int(input())
for _ in range(t):
    n,k = map(int,input().split())
    s = input()
    m = [0]*26
    for a in s:
        m[ord(a)-ord('a')]+=1
    t = max(m)
    x = t*k
    while True:
        b = x//(gcd(x,k))
        count = 0
        for a in m:
            count+=a//b
        if count*b>=x:
            break
        x-=1
    print(x)

import math
t=int(input())
for _ in range(t):
  n,k=map(int,input().split())
  s=input()
  slist=[]
  for i in range(n):
    slist.append(s[i])
  slist.sort()
  slist2=[]
  slist2.append([slist[0],1])
  for i in range(1,len(s)):
    if slist2[-1][0]==slist[i]:
      slist2[-1][1]+=1
    else:
      slist2.append([slist[i],1])
  maxans=1
  for i in range(2,n+1):
    b=math.gcd(i,k)
    a=i//b
    while (a+1)*b<=i:
      a+=1
    temp=0
    for j in range(len(slist2)):
      c=slist2[j][1]//a
      while (c+1)*a<=slist2[j][1]:
        c+=1
      temp+=c
    if temp>=b:
      maxans=i
  print(maxans)

import sys

inp = [x for x in sys.stdin.read().split()]; ii = 0

ttt = int(inp[ii]); ii += 1
for _ in range(ttt):
	n, k, s = int(inp[ii]), int(inp[ii + 1]), inp[ii + 2]; ii += 3
	cnt = [0] * 26
	for c in s:
		cnt[ord(c) - ord('a')] += 1
	res = 1
	for d in range(1, k + 1):
		if k % d == 0:
			for l in range(d, n + 1, d):
				q = l // d
				counter = 0
				for x in cnt:
					counter += x // q
				if counter >= d:
					res = max(res, l)
	print(res)

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def find(cnt, k, h):
	l = 0
	r = 2001
	while r-l > 1:
		now = 0
		c = (l + r) // 2
		for j in cnt:
			now += j//c
		if now >= h:
			l = c
		else:
			r = c
	return l*h

def solve():
	n, k = mints()
	cnt = [0] * 26
	for i in minp():
		cnt[ord(i) - ord('a')] += 1
	cnt.sort(reverse = True)
	ans = 0
	for i in range(1,k+1):
		if k % i == 0:
			ans = max(ans, find(cnt, k, i))
			if k // i != i:
				ans = max(ans, find(cnt, k, k // i))
	print(ans)

for i in range(mint()):
	solve()


T = int(input())

def solve():
    [N,K] = list(map(int,input().split()))
    count = {}
    S = input()
    for c in S:
        if c not in count:
            count[c] = 0
        count[c] += 1

    def necklace_size(m):
        count_ = count.copy()
        ans = [None for _ in range(m)]
        for i in range(len(ans)):
            if ans[i] != None:
                continue
            cyclic_group = set()
            j = i
            while j not in cyclic_group:
                cyclic_group.add(j)
                j += K
                j %= m
            key = None
            val = -1
            for k in count_:
                if count_[k] >= len(cyclic_group):
                    if key == None:
                        key = k
                        val = count_[k]
                    else:
                        if count_[k] < val:
                            key = k
                            val = count_[k]
            if key == None:
                return False
            for i in cyclic_group:
                ans[i] = key
                count_[key] -= 1
        return "".join(ans)
    for i in range(len(S),-1,-1):
        foo = necklace_size(i)
        if foo:
            return len(foo)
    return -1
for _ in range(T):
    print(solve())


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a%b)

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    s = input()
    if s[0] * n == s:
        print(n)
        continue
    cnt = {}
    for c in s:
        if c not in cnt:
            cnt[c] = 0
        cnt[c] += 1
    cnt = [cnt[c] for c in cnt]
    ans = 1
    for x in range(2,n+1):
        tempK = k % x
        if tempK == 0:
            ans = max(ans, x)
            continue
        mod = x % tempK
        if mod != 0:
            mod = -(mod - tempK)
        times = tempK // gcd(tempK, mod)
        needed = x*times // tempK
        usedBeads = 0
        for num in cnt:
            usedBeads += num - num % needed
        if usedBeads >= x:
            ans = max(ans, x)
    print(ans)