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".
[{"code": "t = int(input())\ndef gcd(a,b):\n    if b == 0:\n        return a\n    return gcd(b,a%b)\nfor _ in range(t):\n    n,k = map(int,input().split())\n    s = input()\n    occ = [0] * 26\n    for i in s:\n        occ[ord(i)-97] += 1\n    occ.sort()\n    occ.reverse()\n    for l in range(1,n+1):\n        cycle = gcd(l,k)\n        need = l//cycle\n        su = 0\n        for i in occ:\n            su += i//need\n        if su*need >= l:\n            wyn = l\n    print(wyn)", "passed": true, "time": 0.44, "memory": 14100.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\nfrom math import gcd\n\nt=int(input())\nfor tests in range(t):\n    n,k=list(map(int,input().split()))\n    S=input().strip()\n\n    LIST=[0]*26\n    for s in S:\n        LIST[ord(s)-97]+=1\n\n    for x in range(n,0,-1):\n        GCD=gcd(x,k)\n        p=x//GCD\n\n        SUM=0\n        for l in LIST:\n            if l>=p:\n                SUM+=l//p*p\n\n        if SUM>=x:\n            print(x)\n            break\n\n    #print(S)\n            \n\n        \n        \n", "passed": true, "time": 0.14, "memory": 14092.0, "status": "done"}, {"code": "import math\nt = int(input())\nfor _ in range(t):\n    n,k = list(map(int,input().split()))\n    s = input()\n    countLetters = [0] * 26\n    for elem in s:\n        countLetters[ord(elem) - ord('a')] += 1\n    factors = []\n    for i in range(1,int(math.sqrt(k)) + 1):\n        if k % i == 0:\n            factors.append(i)\n            factors.append(k//i)\n    groups = []\n    for i in range(1,n+1):\n        sumBeads = 0\n        for elem in countLetters:\n            sumBeads += elem // i\n        groups.append(sumBeads)\n    maxNecklace = 0\n    for elem in factors:\n        maxGroup = 0\n        for i in range(n):\n            if groups[i] < elem:\n                break\n            else:\n                maxGroup = i + 1\n        if maxNecklace < maxGroup * elem:\n            maxNecklace = maxGroup * elem\n    print(maxNecklace)\n\n\n\n", "passed": true, "time": 0.14, "memory": 14108.0, "status": "done"}, {"code": "def gcd(a,b):\n    if b==0:\n        return a\n    else:\n        return gcd(b,a%b)\n\n\n\nt = int(input())\nfor _ in range(t):\n    n,k = map(int,input().split())\n    s = input()\n    m = [0]*26\n    for a in s:\n        m[ord(a)-ord('a')]+=1\n    t = max(m)\n    x = t*k\n    while True:\n        b = x//(gcd(x,k))\n        count = 0\n        for a in m:\n            count+=a//b\n        if count*b>=x:\n            break\n        x-=1\n    print(x)", "passed": true, "time": 0.45, "memory": 14372.0, "status": "done"}, {"code": "import math\nt=int(input())\nfor _ in range(t):\n  n,k=map(int,input().split())\n  s=input()\n  slist=[]\n  for i in range(n):\n    slist.append(s[i])\n  slist.sort()\n  slist2=[]\n  slist2.append([slist[0],1])\n  for i in range(1,len(s)):\n    if slist2[-1][0]==slist[i]:\n      slist2[-1][1]+=1\n    else:\n      slist2.append([slist[i],1])\n  maxans=1\n  for i in range(2,n+1):\n    b=math.gcd(i,k)\n    a=i//b\n    while (a+1)*b<=i:\n      a+=1\n    temp=0\n    for j in range(len(slist2)):\n      c=slist2[j][1]//a\n      while (c+1)*a<=slist2[j][1]:\n        c+=1\n      temp+=c\n    if temp>=b:\n      maxans=i\n  print(maxans)", "passed": true, "time": 0.14, "memory": 14376.0, "status": "done"}, {"code": "import sys\n\ninp = [x for x in sys.stdin.read().split()]; ii = 0\n\nttt = int(inp[ii]); ii += 1\nfor _ in range(ttt):\n\tn, k, s = int(inp[ii]), int(inp[ii + 1]), inp[ii + 2]; ii += 3\n\tcnt = [0] * 26\n\tfor c in s:\n\t\tcnt[ord(c) - ord('a')] += 1\n\tres = 1\n\tfor d in range(1, k + 1):\n\t\tif k % d == 0:\n\t\t\tfor l in range(d, n + 1, d):\n\t\t\t\tq = l // d\n\t\t\t\tcounter = 0\n\t\t\t\tfor x in cnt:\n\t\t\t\t\tcounter += x // q\n\t\t\t\tif counter >= d:\n\t\t\t\t\tres = max(res, l)\n\tprint(res)", "passed": true, "time": 0.17, "memory": 14124.0, "status": "done"}, {"code": "import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef mint():\n\treturn int(minp())\n\ndef mints():\n\treturn list(map(int, minp().split()))\n\ndef find(cnt, k, h):\n\tl = 0\n\tr = 2001\n\twhile r-l > 1:\n\t\tnow = 0\n\t\tc = (l + r) // 2\n\t\tfor j in cnt:\n\t\t\tnow += j//c\n\t\tif now >= h:\n\t\t\tl = c\n\t\telse:\n\t\t\tr = c\n\treturn l*h\n\ndef solve():\n\tn, k = mints()\n\tcnt = [0] * 26\n\tfor i in minp():\n\t\tcnt[ord(i) - ord('a')] += 1\n\tcnt.sort(reverse = True)\n\tans = 0\n\tfor i in range(1,k+1):\n\t\tif k % i == 0:\n\t\t\tans = max(ans, find(cnt, k, i))\n\t\t\tif k // i != i:\n\t\t\t\tans = max(ans, find(cnt, k, k // i))\n\tprint(ans)\n\nfor i in range(mint()):\n\tsolve()\n", "passed": true, "time": 0.14, "memory": 14376.0, "status": "done"}, {"code": "T = int(input())\n\ndef solve():\n    [N,K] = list(map(int,input().split()))\n    count = {}\n    S = input()\n    for c in S:\n        if c not in count:\n            count[c] = 0\n        count[c] += 1\n\n    def necklace_size(m):\n        count_ = count.copy()\n        ans = [None for _ in range(m)]\n        for i in range(len(ans)):\n            if ans[i] != None:\n                continue\n            cyclic_group = set()\n            j = i\n            while j not in cyclic_group:\n                cyclic_group.add(j)\n                j += K\n                j %= m\n            key = None\n            val = -1\n            for k in count_:\n                if count_[k] >= len(cyclic_group):\n                    if key == None:\n                        key = k\n                        val = count_[k]\n                    else:\n                        if count_[k] < val:\n                            key = k\n                            val = count_[k]\n            if key == None:\n                return False\n            for i in cyclic_group:\n                ans[i] = key\n                count_[key] -= 1\n        return \"\".join(ans)\n    for i in range(len(S),-1,-1):\n        foo = necklace_size(i)\n        if foo:\n            return len(foo)\n    return -1\nfor _ in range(T):\n    print(solve())\n", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "def gcd(a, b):\n    if a < b:\n        return gcd(b, a)\n    if b == 0:\n        return a\n    return gcd(b, a%b)\n\nfor _ in range(int(input())):\n    n, k = list(map(int, input().split()))\n    s = input()\n    if s[0] * n == s:\n        print(n)\n        continue\n    cnt = {}\n    for c in s:\n        if c not in cnt:\n            cnt[c] = 0\n        cnt[c] += 1\n    cnt = [cnt[c] for c in cnt]\n    ans = 1\n    for x in range(2,n+1):\n        tempK = k % x\n        if tempK == 0:\n            ans = max(ans, x)\n            continue\n        mod = x % tempK\n        if mod != 0:\n            mod = -(mod - tempK)\n        times = tempK // gcd(tempK, mod)\n        needed = x*times // tempK\n        usedBeads = 0\n        for num in cnt:\n            usedBeads += num - num % needed\n        if usedBeads >= x:\n            ans = max(ans, x)\n    print(ans)\n", "passed": true, "time": 0.14, "memory": 14308.0, "status": "done"}]