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: HARD
Tags: Graph algorithms

Graph traversal

Complete search

Greedy algorithms

Number theory

Dynamic programming
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	[n, k] = list(map(int, input().split()))
	s = input()
	l = [s.count(a) for a in set(s)]
	M = 0
	for j in range(1, n + 1):
		MM = sum(map(lambda x: x // j, l))
		if MM == 0:
			continue
		while k % MM:
			MM -= 1
		M = max(M, MM * j)
	print(M)


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
for i in range(int(input())):
	(n, k) = map(int, input().split())
	cnt = [0] * 26
	for i in input():
		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)


def good(n, k, letters):
	if letters[-1] >= n:
		return True
	necklace = [-1] * n
	letters_copy = letters[:]
	i = 25
	index = 0
	visited = set()
	while i >= 0:
		indices = set()
		while index not in indices:
			indices.add(index)
			index += k
			index %= n
		if letters_copy[i] >= len(indices):
			letters_copy[i] -= len(indices)
			for j in indices:
				necklace[j] = i
				visited.add(j)
			for j in range(n):
				if j not in visited:
					index = j
					break
		else:
			i -= 1
		if len(visited) == n:
			break
	for j in range(n):
		if necklace[j] == -1:
			return False
		if necklace[j] != necklace[(j + k) % n]:
			return False
	return True

def solve(s, n, k, ans):
	letters = [0] * 26
	for i in s:
		letters[ord(i) - ord('a')] += 1
	letters.sort()
	max_n = 0
	for i in range(1, n + 1):
		if good(i, k, letters):
			max_n = i
	ans.append(max_n)

def main():
	t = int(input())
	ans = []
	for i in range(t):
		(n, k) = map(int, input().split())
		s = input()
		solve(s, n, k, ans)
	for i in ans:
		print(i)
main()


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(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)


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)


from collections import deque
import collections

def solve(n, k, s):
	lettersCounter = collections.Counter(s)
	for m in range(n, 0, -1):
		used = [False] * m
		cycles = deque()
		for i in range(m):
			if used[i]:
				continue
			j = (i + k) % m
			used[i] = True
			cycles.insert(len(cycles), 1)
			while not used[j]:
				cycles[len(cycles) - 1] += 1
				used[j] = True
				j = (j + k) % m
		cycles = list(sorted(cycles))
		count = list(sorted(lettersCounter.values()))
		canDoIt = True
		while cycles:
			if count[len(count) - 1] < cycles[len(cycles) - 1]:
				canDoIt = False
				break
			else:
				count[len(count) - 1] -= cycles[len(cycles) - 1]
				cycles.pop()
				count = sorted(count)
		if canDoIt:
			return m
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(solve(n, k, s))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	s = input()
	count = [0] * 26
	for i in s:
		count[ord(i) - 97] += 1
	count = sorted(count, reverse=True)
	for i in range(n, 0, -1):
		st = set()
		a = []
		for j in range(i):
			jj = j
			count1 = 0
			while jj not in st:
				count1 += 1
				st.add(jj)
				jj = (jj + k) % i
			if count1:
				a += [count1]
		a = sorted(a, reverse=True)
		cc = list(count)
		pos = True
		for each in a:
			f = False
			for ki in range(len(cc)):
				if cc[ki] >= each:
					cc[ki] -= each
					f = True
					break
			if not f:
				pos = False
				break
		if pos:
			print(i)
			break


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input().rstrip())
	l = []
	for i in range(1, int(k ** 0.5) + 1):
		if k % i == 0:
			if i <= n:
				l.append(i)
			if k // i <= n:
				l.append(k // i)
	l = set(l)
	c = [0] * 26
	for ss in s:
		c[ord(ss) - ord('a')] += 1
	ans = 0
	for kk in l:
		for x in range(1, n + 1):
			can = 0
			for i in range(26):
				can += c[i] // x
			if can > 0 and kk % can == 0:
				ans = max(ans, x * can)
			if can >= kk:
				ans = max(ans, x * kk)
	print(ans)


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
from collections import Counter
from itertools import groupby
from math import gcd

def solve(n, k, s):
	sd = sorted(Counter(s).values(), reverse=True)
	ans = 0
	for m in range(1, n + 1):
		d = gcd(m, k)
		d1 = m // d
		if sum([x // d1 for x in sd]) >= d:
			ans = m
	return ans

def main():
	for _ in range(ri()):
		(n, k) = ria()
		s = rs()
		wi(solve(n, k, s))
main()


from collections import Counter
tc = int(input())
while tc:
	(n, k) = map(int, input().split())
	cnt = Counter(input())
	divs = []
	for i in range(1, 1 + int(k ** 0.5)):
		if k % i == 0:
			divs.append(i)
			divs.append(k // i)
	res = 0
	for i in divs:
		rep = 1
		while rep * i <= n:
			c = 0
			for k in cnt:
				c += cnt[k] // rep
			if c >= i:
				res = max(res, rep * i)
			else:
				break
			rep += 1
	print(res)
	tc -= 1


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)


from collections import Counter

def cycleGrouping(length, k):
	groups = [-1 for _ in range(length)]
	currGroupNo = 0
	for i in range(length):
		j = i
		while groups[j] == -1:
			groups[j] = currGroupNo
			j += k
			while j >= length:
				j -= length
		currGroupNo += 1
	groupSizes = list(Counter(groups).values())
	return groupSizes

def checkPossible(freqArr, length, k):
	groupSizes = cycleGrouping(length, k)
	i = 0
	n = len(groupSizes)
	ok = False
	for sz in freqArr:
		while sz >= groupSizes[i]:
			sz -= groupSizes[i]
			i += 1
			if i == n:
				ok = True
				break
		if ok:
			break
	return ok

def main():
	allAns = []
	t = int(input())
	for _ in range(t):
		(n, k) = readIntArr()
		s = input()
		cnts = Counter(s)
		freqArr = list(cnts.values())
		ans = 0
		for length in range(1, n + 1):
			if checkPossible(freqArr, length, k):
				ans = length
		allAns.append(ans)
	multiLineArrayPrint(allAns)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
main()


from collections import Counter
wer = int(input())
for ewr in range(wer):
	(n, m) = list(map(int, input().split(' ')))
	temp = list(input())
	dic = Counter(temp)
	ans = 1
	for i in range(n, 0, -1):
		t = m % i
		if t == 0:
			ans = i
			break
		else:
			flag = 0
			for k in range(1, t + 1):
				if t % k != 0:
					continue
				te = t // k
				if i % te != 0:
					continue
				else:
					p = i // te
					for j in dic:
						v = dic[j]
						te -= dic[j] // p
					if te < 1:
						flag = 1
						ans = i
						break
			if flag == 1:
				break
	print(ans)


from math import gcd
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	freq = [0 for i in range(26)]
	for _ in s:
		freq[ord(_) - ord('a')] += 1
	freq.sort()
	ans = 1
	for len in range(2, n + 1):
		g = gcd(k, len)
		sz = len // g
		count = 0
		for each in freq:
			count += each // sz
		if count * sz >= len:
			ans = len
	print(ans)


import sys

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

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

def mints():
	return map(int, input().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
for i in range(mint()):
	(n, k) = map(int, input().split())
	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 _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	qu = list((0 for i in range(26)))
	qu.sort()
	ans = 0
	for m in range(1, n + 1):
		qu = list((0 for i in range(26)))
		for i in s:
			qu[ord(i) - ord('a')] += 1
		p = list((0 for i in range(m)))
		used = list((False for i in range(m)))
		for i in range(m):
			p[i] = (i + k) % m
		cycle = list()
		for i in range(m):
			if not used[i]:
				h = i
				an = 0
				while not used[h]:
					used[h] = True
					h = p[h]
					an += 1
				cycle.append(an)
		cycle.sort()
		index = 0
		i = 0
		while True:
			if index == 26:
				break
			if i == len(cycle):
				ans = m
				break
			if cycle[i] > qu[index]:
				index += 1
				continue
			qu[index] -= cycle[i]
			i += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		cnt = [0] * 26
		for x in s:
			cnt[ord(x) - ord('a')] += 1
		cnt.sort(reverse=True)

		def chk(n):
			vis = [False] * n
			b = []
			for i in range(n):
				if vis[i]:
					continue
				cur = 0
				while not vis[i]:
					cur += 1
					vis[i] = True
					i = (i + k) % n
				b.append(cur)
			a = []
			for x in cnt:
				if x:
					a.append(x)
				else:
					break
			b.sort(reverse=True)
			for x in b:
				if x > a[0]:
					return False
				a[0] -= x
				a.sort(reverse=True)
			return True
		for l in reversed(range(n + 1)):
			if not chk(l):
				continue
			print(l)
			break
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import gcd

def main():
	(n, k) = map(int, input().split())
	st = input()
	alph = [0 for i in range(ord('z') - ord('a') + 1)]
	for i in st:
		alph[ord(i) - ord('a')] += 1
	for i in range(n, 0, -1):
		n2 = gcd(i, k)
		n1 = i // n2
		for j in alph:
			n2 -= j // n1
		if n2 <= 0:
			print(i)
			return
for t in range(int(input())):
	main()


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
from math import *
import copy
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def bo(i):
	return ord(i) - ord('a')
from copy import *
from bisect import *
from itertools import permutations

def can(mid, k):
	c = i = 0
	while i < p and c < k:
		if d[i] < mid // k:
			return False
		c += d[i] // (mid // k)
		i += 1
	return True * (c >= k)
tt = fi()
while tt > 0:
	tt -= 1
	(n, k) = mi()
	s = si()
	d = [0 for i in range(26)]
	for i in s:
		d[bo(i)] += 1
	d.sort(reverse=True)
	if d.count(0) > 0:
		d = d[:d.index(0)]
	p = len(d)
	ans = max(d)
	for i in range(1, n + 1):
		if can(i, gcd(k, i)):
			ans = i
	print(ans)


from functools import cmp_to_key
from collections import deque
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def sli():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)

def custom_sort(lista):

	def cmp(x, y):
		if x + y > y + x:
			return 1
		else:
			return -1
	return sorted(lista, key=cmp_to_key(cmp))
MOD = 10 ** 9 + 7
maxN = 10 ** 5
FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def coeffBinom(n, k):
	if n < k:
		return 0
	return divide(FACT[n], multiply(FACT[k], FACT[n - k]))

def primes(N):
	smallest_prime = [1] * (N + 1)
	prime = []
	smallest_prime[0] = 0
	smallest_prime[1] = 0
	for i in range(2, N + 1):
		if smallest_prime[i] == 1:
			prime.append(i)
			smallest_prime[i] = i
		j = 0
		while j < len(prime) and i * prime[j] <= N:
			smallest_prime[i * prime[j]] = min(prime[j], smallest_prime[i])
			j += 1
	return (prime, smallest_prime)

def gcd(a, b):
	a = abs(a)
	b = abs(b)
	(s, t, r) = (0, 1, b)
	(old_s, old_t, old_r) = (1, 0, a)
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return (old_r, old_s, old_t)

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def create_edges(m, unweighted=0):
	edges = list()
	if unweighted:
		for i in range(m):
			edges.append(li(lag=-1))
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			edges.append([w, x, y])
	return edges

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def connected(graph, n):
	v = dfs(graph, n, 0)
	for el in v:
		if el == -1:
			return False
	return True

def topological(graph, n):
	indegree = [0] * n
	for el in range(n):
		for child in graph[el]:
			indegree[child] += 1
	s = deque()
	for el in range(n):
		if indegree[el] == 0:
			s.append(el)
	order = []
	while s:
		el = s.popleft()
		order.append(el)
		for child in graph[el]:
			indegree[child] -= 1
			if indegree[child] == 0:
				s.append(child)
	if n == len(order):
		return (False, order)
	else:
		return (True, [])

def bipartite(graph, n):
	color = [-1] * n
	color[0] = 0
	s = [0]
	while s:
		el = s.pop()
		for child in graph[el]:
			if color[child] == color[el]:
				return False
			if color[child] == -1:
				s.append(child)
			color[child] = 1 - color[el]
	return True

def dijkstra(graph, n, A):
	dist = [float('inf') for i in range(n)]
	prev = [-1 for i in range(n)]
	dist[A] = 0
	pq = []
	heappush(pq, [0, A])
	while pq:
		[d_v, v] = heappop(pq)
		if d_v != dist[v]:
			continue
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
				prev[to] = v
				heappush(pq, [dist[to], to])
	return (dist, prev)

def dijkstra_0_1(graph, n, A):
	dist = [float('inf') for i in range(n)]
	dist[A] = 0
	p = deque()
	p.append(A)
	while p:
		v = p.popleft()
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
			if w == 1:
				q.append(to)
			else:
				q.appendleft(to)
	return dist

def floyd_warshall(graph, n):
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for (child, d) in graph[i]:
			dist[i][child] = d
			dist[child][i] = d
	for k in range(n):
		for i in range(n):
			for j in range(j):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

def minimum_spanning_tree(edges, n):
	edges = sorted(edges)
	union_find = UnionFind(n)
	used_edges = list()
	for (w, x, y) in edges:
		if union_find.find(x) != union_find.find(y):
			union_find.merge(x, y)
			used_edges.append([w, x, y])
	return used_edges

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def finding_ancestors(parent, queries, n):
	steps = int(ceil(log(n, 2)))
	ancestors = [[-1 for i in range(n)] for j in range(steps)]
	ancestors[0] = parent
	for i in range(1, steps):
		for node in range(n):
			if ancestors[i - 1][node] != -1:
				ancestors[i][node] = ancestors[i - 1][ancestors[i - 1][node]]
	result = []
	for (node, k) in queries:
		ans = node
		if k >= n:
			ans = -1
		i = 0
		while k > 0 and ans != -1:
			if k % 2:
				ans = ancestors[i][ans]
			k = k // 2
			i += 1
		result.append(ans)
	return result

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def nearest_from_the_left_smaller_elements(arr):
	n = len(arr)
	res = [-1] * n
	s = []
	for (i, el) in enumerate(arr):
		while s and s[-1] >= el:
			s.pop()
		if s:
			res[i] = s[-1]
		s.append(el)
	return res

def sliding_window_minimum(arr, k):
	res = []
	q = deque()
	for (i, el) in enumerate(arr):
		while q and arr[q[-1]] >= el:
			q.pop()
		q.append(i)
		while q and q[0] <= i - k:
			q.popleft()
		if i >= k - 1:
			res.append(arr[q[0]])
	return res

def f(n, k, s):
	c = [0] * 26
	for i in range(n):
		c[ord(s[i]) - ord('a')] += 1
	c = sorted(c, reverse=True)
	k1 = k
	for m in range(n, 0, -1):
		k = k1 % m + (m if k1 % m == 0 else 0)
		s = set()
		for i in range(m):
			s.add(i * k % m)
		l = len(s)
		if l * k % m == 0:
			somma = 0
			for el in c:
				somma += el // l * l
			if somma >= m:
				return m
	return 1
for test in range(ii()):
	(n, k) = li()
	s = str(inp())
	print(f(n, k, s))


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = Counter(input())
	val = sorted(list(c.values()), reverse=True)
	length = len(val)
	ans = 0
	for i in range(1, k + 1):
		if k % i == 0:
			for l in range(i, n + 1, i):
				temp = 0
				each = l // i
				for j in range(length):
					temp += val[j] // each
				if temp >= i:
					ans = max(ans, l)
				else:
					break
	print(ans)


import math
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split(' '))
	(s, cnt, an) = (input(), [], 0)
	for i in range(26):
		cnt.append(0)
	for el in s:
		cnt[ord(el) - ord('a')] += 1
	for i in range(1, n + 1):
		gc = math.gcd(i, k)
		(ln, sm) = (i / gc, 0)
		for el in cnt:
			sm += el // ln
		if sm >= gc:
			an = max(an, i)
	print(an)


import sys
from collections import Counter
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def factor(a):
	if a == 1:
		return [1]
	res = []
	for d in range(1, a + 1):
		if d ** 2 > a:
			break
		if a % d == 0:
			res.append(d)
			res.append(a // d)
		if res[-1] == res[-2]:
			res.pop()
	return res

def main():
	inf = 10 ** 9
	for _ in range(II()):
		(n, k) = MI()
		ca = Counter(SI())
		aa = list(ca.values())
		aa.sort(reverse=True)
		mns = [inf] * len(aa)
		for (i, a) in enumerate(aa):
			mns[i] = min(a, mns[i - 1])
		ans = 0

		def ok(m):
			cnt = 0
			for a in aa:
				if a < m:
					return False
				cnt += a // m
				if cnt >= f:
					return True
		for f in factor(k):
			l = 0
			r = 2001
			while l + 1 < r:
				m = (l + r) // 2
				if ok(m):
					l = m
				else:
					r = m
			ans = max(ans, l * f)
		print(ans)
main()


from math import gcd
from collections import Counter
for _ in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	s = input()
	(ctr, result) = (Counter(s), 0)
	for i in range(1, n + 1):
		l = i // gcd(i, k)
		cnt = sum([v // l * l for v in ctr.values()])
		if cnt >= i:
			result = i
	print(result)


from collections import Counter
from math import gcd
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	str = input()
	ans = 0
	count = Counter(str)
	for i in range(1, n + 1):
		loop = gcd(i, k)
		num = i / loop
		c = 0
		for j in count.values():
			c += j // num
		if c >= loop:
			ans = max(ans, i)
	print(ans)


import math
import collections

def solve(n, k, s):
	ctr = collections.Counter(s)
	for m in range(n, 0, -1):
		g = math.gcd(m, k)
		l = m / g
		count = sum([v // l * l for v in ctr.values()])
		if count >= m:
			print(m)
			break
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	solve(n, k, s)


import math
from sys import stdin

def factors(n):
	f = []
	f2 = []
	for x in range(1, int(n ** 0.5) + 1):
		if n % x == 0:
			f.append(x)
			f2.append(n // x)
	f2 = f2[::-1]
	if f[-1] == f2[0]:
		f += f2[1:]
	else:
		f += f2
	return f
for case in range(int(stdin.readline())):
	mem = {}
	(n, k) = [int(x) for x in stdin.readline().split()]
	s = stdin.readline().strip()
	chars = {}
	for x in s:
		if x in chars:
			chars[x] += 1
		else:
			chars[x] = 1
	c = []
	for x in chars:
		c.append((chars[x], x))
	c.sort()
	best = c[-1][0]
	for x in range(best + 1, n + 1):
		period = k % x
		if period == 0:
			best = x
		else:
			for y in factors(period):
				if x % y == 0:
					div = x // y
					need = 0
					for (num, l) in c:
						need += num // div
					if need >= y:
						best = x
	print(best)


import math

def modinv(n, p):
	return pow(n, p - 2, p)

def main():
	for case in range(int(input())):
		(n, k) = [int(x) for x in input().split()]
		s = input()
		letters = {}
		for c in s:
			try:
				letters[c] += 1
			except:
				letters[c] = 1
		temp = []
		for key in letters.keys():
			temp.append([letters[key], key])
		temp.sort(reverse=True)
		for l in range(n, 0, -1):
			d = math.gcd(l, k)
			count_per_bead = l // d
			n_beads = d
			c = 0
			for p in temp:
				c += p[0] // count_per_bead
			if c >= n_beads:
				print(l)
				break
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
num_tests = int(input())

def calc_num_least(letters, x):
	count = 0
	for letter in letters:
		if letters[letter] >= x:
			count += letters[letter] // x
	return count

def solve(n, k, letters):
	best = 0
	for i in range(1, n + 1):
		j = calc_num_least(letters, i)
		for x in reversed(range(1, j + 1)):
			if k % x == 0:
				best = max(best, x * i)
				break
	return best
for test in range(num_tests):
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	letters = {}
	for i in s:
		letters[i] = letters.get(i, 0) + 1
	print(solve(n, k, letters))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	dict = {}
	ans = 0
	for i in range(len(s)):
		if dict.get(ord(s[i]) - 97) is None:
			dict[ord(s[i]) - 97] = 0
		dict[ord(s[i]) - 97] += 1
	for i in range(1, k + 1):
		if k % i == 0:
			for j in range(i, n + 1, i):
				lol = j // i
				count = 0
				for p in range(26):
					if dict.get(p) is None:
						continue
					count += dict[p] // lol
				if count >= i:
					ans = max(ans, j)
	print(ans)


import math
from fractions import gcd
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	D = list(input())
	counts = []
	for el in set(D):
		counts.append(D.count(el))
	counts.sort(reverse=True)
	if True:
		maxx = 0
		for j in range(1, b + 1):
			if b % j == 0:
				for k in range(1, max(counts) + 1):
					tot = 0
					for el in range(min(j, len(counts))):
						tot += counts[el] // k
					if tot >= j:
						maxx = max(maxx, j * k)
	else:
		for j in range(1, a + 1):
			if b % j == 0:
				maxx = j
	print(maxx)


from sys import stdin
import math
import sys
for _ in range(int(stdin.readline())):
	(N, k) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	dictt = {}
	for i in s:
		if i not in dictt:
			dictt[i] = 1
		else:
			dictt[i] += 1
	ans = 1
	for n in range(N, 1, -1):
		kt = k % n
		if kt == 0:
			ans = n
			break
		g = math.gcd(n, kt)
		req = n / g
		count = 0
		for i in dictt:
			count += dictt[i] // req
		if count >= g:
			ans = n
			break
	print(ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def check(have, m, k):
	if k % m == 0:
		return True
	k %= m
	cycle = [-1 for i in range(m)]
	for i in range(m):
		if cycle[i] < 0:
			(a, b) = (i, (i + k) % m)
			size = 0
			while cycle[a] < 0:
				size += 1
				cycle[a] = b
				(a, b) = (b, (b + k) % m)
			(ti, diff) = (-1, 5000)
			for (hi, hv) in enumerate(have):
				d = hv - size
				if 0 <= d < diff:
					diff = d
					ti = hi
			if ti < 0:
				return False
			have[ti] -= size
	return True

def solve(N, K, S):
	wc = collections.Counter(S)
	have = list(wc.values())
	have.sort(reverse=True)
	ans = 0
	for p in range(1, K + 1):
		if K % p != 0:
			continue
		if p > K:
			break
		for m in range(N, ans, -1):
			if check(have.copy(), m, p):
				ans = max(ans, m)
				break
	return ans
T = int(input())
ans = []
for ti in range(T):
	(N, K) = map(int, input().split())
	S = list(input())
	ans.append(solve(N, K, S))
print('\n'.join(map(str, ans)))


from collections import Counter

def getAllFactors(x):
	factors = []
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			factors.append(i)
			if x // i != i:
				factors.append(x // i)
	return sorted(factors)

def checkPossible(nCycles, lastItem, freqArr, k):
	if lastItem >= k:
		return False
	nItemsFilled = 0
	for item in range(lastItem + 1):
		cnt = freqArr[item]
		nItemsFilled += cnt // nCycles
	return nItemsFilled >= k

def getAns(k, freqArr):
	maxCycles = 0
	for lastItem in range(min(k, len(freqArr))):
		b = 2000
		nCycles = 0
		while b > 0:
			while checkPossible(nCycles + b, lastItem, freqArr, k):
				nCycles += b
			b //= 2
		maxCycles = max(maxCycles, nCycles)
	ans = maxCycles * k
	return ans

def main():
	allAns = []
	t = int(input())
	for _ in range(t):
		(n, k) = readIntArr()
		s = input()
		cnts = Counter(s)
		freqArr = list(cnts.values())
		freqArr.sort(reverse=True)
		ans = 0
		factors = getAllFactors(k)
		for f in factors:
			ans = max(ans, getAns(f, freqArr))
		allAns.append(ans)
	multiLineArrayPrint(allAns)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
main()


from collections import Counter
T = int(input())

def possible(m, K, cc):
	answer = 0
	for v in cc:
		answer += v // m
	return answer >= K
for t in range(T):
	(N, K) = [int(_) for _ in input().split()]
	S = input()
	cc = [i[1] for i in Counter(S).most_common()]
	answer = 0
	for k in range(1, K + 1):
		if K % k == 0:
			(l, r) = (1, 2000)
			while l <= r:
				m = (l + r) // 2
				if possible(m, k, cc):
					l = m + 1
					answer = max(answer, m * k)
				else:
					r = m - 1
	print(answer)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count = [0] * 26
	for ch in s:
		count[ord(ch) - ord('a')] += 1
	count.sort()
	res = 1
	for i in range(2, n + 1):
		g = math.gcd(i, k)
		l = i // g
		ans = 0
		for x in count:
			ans += x // l
		if ans * l >= i:
			res = i
	print(res)


import math

def tellFactorsOfK(k):
	sq = int(math.sqrt(k))
	liAns = []
	for i in range(1, sq + 2):
		if k % i == 0:
			liAns.append(i)
			liAns.append(k // i)
	liSet = set()
	liNoDuplicate = []
	for i in liAns:
		if i not in liSet:
			liSet.add(i)
			liNoDuplicate.append(i)
	liNoDuplicate.sort()
	return liNoDuplicate

def isPossibleNecklace(liFreq, size, baseSize):
	multipyBy = size // baseSize
	s = 0
	a = baseSize
	for i in liFreq:
		s += i[1] // multipyBy
		if s >= a:
			return True
	if s >= a:
		return True
	return False

def tellMaxOfOneFactor(liFreq, factor, n):
	ans = -1
	multiplyBy = 1
	while multiplyBy * factor <= n + 1:
		if isPossibleNecklace(liFreq, multiplyBy * factor, factor):
			ans = multiplyBy * factor
		multiplyBy += 1
	return ans
for _ in range(int(input())):
	liStr = input().split()
	n = int(liStr[0])
	k = int(liStr[1])
	s = input()
	liS = list(s)
	diFreq = {}
	for i in s:
		diFreq[i] = diFreq.get(i, 0) + 1
	liFreq = []
	for i in diFreq:
		liTemp = []
		liTemp.append(i)
		liTemp.append(diFreq[i])
		liFreq.append(liTemp)
	liFreq.sort(key=lambda x: x[1], reverse=True)
	liFactorsOfK = tellFactorsOfK(k)
	maxLen = -1
	for factor in liFactorsOfK:
		a = tellMaxOfOneFactor(liFreq, factor, n)
		if a == -1:
			continue
		if a > maxLen:
			maxLen = a
	print(maxLen)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	dic = {}
	for i in st:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	li = list(dic.values())
	li.sort()
	ans = 1
	for i in range(n, 0, -1):
		xx = k % i
		lc = i * xx // math.gcd(i, xx)
		if xx == 0:
			ans = i
			break
		elif lc == i * xx:
			if li[-1] >= i:
				ans = i
				break
		else:
			yy = lc // xx
			count = 0
			for j in li:
				count += j // yy
			if yy * count >= i:
				ans = i
				break
	print(ans)


import sys
import math

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	(n, k) = MI()
	s = input()
	d = [0] * 26
	for i in s:
		d[ord(i) - 97] += 1
	d.sort(reverse=True)
	p = []
	ans = 0
	for i in range(1, n + 1):
		a = i // math.gcd(i, k)
		temp = 0
		for j in d:
			temp += j // a * a
		if temp >= i:
			ans = i
	print(ans)


from collections import *
import sys

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

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
t = ri()
for _ in range(t):
	(n, k) = rl()
	s = input()
	cnt = Counter(s)
	ans = 0
	for m in range(n, 0, -1):
		g = gcd(m, k)
		cycle_length = m // g
		nb_cycle = 0
		for key in cnt.keys():
			nb_cycle += cnt[key] // cycle_length
			if nb_cycle >= g:
				ans = m
				break
		if ans == m:
			break
	print(ans)


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
input = sys.stdin.readline
from math import gcd
t = int(input())
for tests in range(t):
	(n, k) = 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


import sys
import math
import heapq
import collections

def inputnum():
	return int(input())

def inputnums():
	return map(int, input().split())

def inputlist():
	return list(map(int, input().split()))

def inputstring():
	return [x for x in input()]

def inputmatrixchar(rows):
	arr2d = [[j for j in input().strip()] for i in range(rows)]
	return arr2d

def inputmatrixint(rows):
	arr2d = []
	for _ in range(rows):
		arr2d.append([int(i) for i in input().split()])
	return arr2d

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
for q in range(t):
	(n, k) = inputnums()
	s = inputstring()
	d = {}
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = 1
		else:
			d[s[i]] += 1
	for i in reversed(range(1, n + 1)):
		t = i / computeGCD(i, k)
		cnt = 0
		for key in d:
			cnt += d[key] // t
		if cnt * t >= i:
			print(i)
			break


import sys
input = sys.stdin.readline
from collections import *

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(n, k_) = map(int, input().split())
	s = input()[:-1]
	cnt = Counter(s)
	ans = 1
	for i in range(1, n + 1):
		k = k_ % i
		g = gcd(i, k)
		same = i // g
		c = 0
		for v in cnt.values():
			c += v // same
		if c >= g:
			ans = i
	print(ans)


import math
test = int(input())
for t in range(0, test):
	(n, k) = map(int, input().split())
	s = input()
	count = [0 for i in range(0, 26)]
	for ch in s:
		count[ord(ch) - ord('a')] += 1
	count.sort()
	fin = 1
	for m in range(2, n + 1):
		c = math.gcd(m, k)
		d = m // c
		ans = 0
		for x in count:
			ans += x // d
		if ans * d >= m:
			fin = m
	print(fin)


import math
from collections import defaultdict

def getDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	return ans
t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	s = str(input())
	maxx = 0
	freq = defaultdict(int)
	for i in range(n):
		freq[s[i]] += 1
	fact = getDivisors(k)
	for lenn in fact:
		for l in range(lenn, n + 1, lenn):
			possible = 0
			each = l // lenn
			for f in freq.values():
				possible += f // each
			if possible >= lenn:
				maxx = max(maxx, l)
			else:
				break
	print(maxx)
	t -= 1


import math
from collections import Counter

def main(n, k, s):
	cnt = Counter(s)
	for l in range(n, 0, -1):
		t = l / math.gcd(l, k)
		s = sum((v // t * t for v in cnt.values()))
		if s >= l:
			return l
for _ in range(int(input())):
	print(main(*map(int, input().split()), input()))


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	t = input()
	fr = [0] * 27
	for i in t:
		x = ord(i) - 97
		fr[x] = fr[x] + 1
	max1 = int(0)
	for i in range(1, len(t) + 1):
		x = math.gcd(i, k)
		p = int(i / x)
		su = int(0)
		for j in range(26):
			su = su + fr[j] - fr[j] % p
		if su < i:
			continue
		max1 = max(max1, i)
	print(max1)


from collections import Counter

def factors(n):
	ret = []
	for i in range(1, n + 1):
		if n % i == 0:
			ret += [i]
	return ret

def ok(S, f, i):
	numPiles = 0
	for s in S:
		numPiles += s // i
	return f <= numPiles

def maxCopies(S, f):
	for i in range(1, 10000000):
		if not ok(S, f, i):
			return i - 1
	assert False

def ans(S, K):
	ret = float('-inf')
	for f in factors(K):
		ret = max(ret, f * maxCopies(S, f))
	return ret
T = int(input())
for t in range(T):
	(N, K) = input().split(' ')
	K = int(K)
	S = input()
	S = sorted(list(Counter(S).values()))[::-1]
	print(ans(S, K))


from collections import Counter
from heapq import heappush, heappop
from copy import deepcopy
for t in range(int(input())):
	(m, k_) = [int(j) for j in input().split()]
	s = list(input())
	d = dict()
	for i in range(m):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	freq = list(sorted(d.values()))
	for n in range(m, 0, -1):
		cyc = []
		vis = [False for i in range(n)]
		k = k_ % n
		for i in range(n):
			if vis[i] == True:
				continue
			j = i
			cyc.append(0)
			while vis[j] == False:
				vis[j] = True
				cyc[-1] += 1
				j = (j + k) % n
		f = deepcopy(freq)
		cyc.sort()
		can_fill = True
		while cyc:
			if cyc[-1] > f[-1]:
				can_fill = False
				break
			f[-1] -= cyc[-1]
			cyc = cyc[:-1]
			f.sort()
		if can_fill:
			print(n)
			break


import sys
import heapq
import random
import collections
import bisect
from functools import reduce

def all_divisors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def solve(k, lst):
	console('----- solving ------')
	c = collections.Counter(lst).values()
	res = 0
	div = [0] + sorted(all_divisors(k)) + [999999999]
	for r in range(1, 2001):
		eligible = [x // r for x in c]
		bis = div[bisect.bisect_right(div, sum(eligible)) - 1]
		res = max(res, bis * r)
	return res

def console(*args):
	print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)
	return
for case_num in range(int(input())):
	(_, k) = list(map(int, input().split()))
	lst = input()
	res = solve(k, lst)
	print(res)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	mp = [0 for i in range(26)]
	for i in s:
		mp[ord(i) - ord('a')] += 1
	mp.sort()
	mp = mp[-1::-1]
	ans = 0
	for i in range(1, n + 1):
		m = i
		cnt = 0
		temp = [-1 for i in range(m)]
		for j in range(m):
			if temp[j] == -1:
				ind = j
				while True:
					if temp[ind] != -1:
						break
					temp[ind] = cnt
					ind += k
					ind = ind % m
				cnt += 1
			else:
				temp[(j + k) % m] = temp[j]
		freq = [0 for j in range(max(temp) + 1)]
		for j in temp:
			freq[j] += 1
		freq.sort()
		freq = freq[-1::-1]
		overall = mp[:]
		for j in freq:
			f = 0
			for p in range(len(overall)):
				if j <= overall[p]:
					overall[p] -= j
					f = 1
					break
			if f == 0:
				break
		if f == 1:
			ans = max(ans, i)
	print(ans)


def check(x):
	add = 0
	for i in range(26):
		add += alpha[i] // x
	return add

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	alpha = [0 for i in range(26)]
	st = input()
	for i in range(n):
		alpha[ord(st[i]) - 97] += 1
	maxi = 0
	for i in range(1, n + 1):
		if i <= m:
			if m % i == 0:
				j = 1
				maxi = max(maxi, i)
				while True:
					q = check(j)
					if q < i:
						break
					maxi = max(maxi, i * j)
					j += 1
		else:
			r = gcd(i, m)
			if r >= 1:
				s = max(m, i) // r
				p = check(s)
				if p >= r:
					maxi = max(maxi, i)
	print(maxi)


from math import *
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	dic = dict()
	for i in s:
		dic[i] = 0
	for i in s:
		dic[i] += 1
	t = sorted(dic.values(), reverse=True)
	r = 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
				r = max(r, y * x)
				y += 1
	print(r)


rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : [int(x) for x in rr().split()]
from sys import stdin, stdout

def sol():
	(n, k) = rrm()
	s = input().strip()
	fr = [0 for i in range(26)]
	for c in s:
		fr[ord(c) - ord('a')] += 1
	res = 1
	for i in range(1, k + 1):
		if k % i == 0:
			x = 1
			while True:
				cn = x * i
				z = 0
				for j in fr:
					z += j // x
				if z < i:
					break
				x += 1
			x -= 1
			res = max(res, x * i)
	print(res)
	return
T = rri()
for t in range(1, T + 1):
	ans = sol()


def possible(n, brr, k):
	chk = []
	visited = [0] * n
	for i in range(n):
		cnt = 0
		if visited[i] == 0:
			visited[i] = 1
			j = (i + k) % n
			cnt += 1
			while j != i:
				visited[j] = 1
				cnt += 1
				j = (j + k) % n
		chk.append(cnt)
	i = 0
	j = 0
	while i < len(chk) and j < len(brr):
		if chk[i] <= brr[j]:
			brr[j] -= chk[i]
			i += 1
		else:
			j += 1
	if i != len(chk):
		return False
	return True
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		d[i] = d.get(i, 0) + 1
	arr = list(d.values())
	arr.sort(reverse=True)
	ans = -1
	for i in range(n, 0, -1):
		brr = arr.copy()
		if possible(i, brr, k):
			ans = i
			break
	print(ans)


import os
inp = os.read(0, int(10000000.0)).split()
inp_pos = -1

def cin():
	global inp_pos
	inp_pos += 1
	return inp[inp_pos]
from itertools import groupby
from math import gcd
T = int(cin())
res = []
while T:
	T -= 1
	n = int(cin())
	k = int(cin())
	a = [len(list(g)) for (k, g) in groupby(sorted(cin()))]
	ans = 0
	for v in range(1, n + 1):
		d = gcd(v, k)
		f = v // d
		if sum([x // f for x in a]) >= d:
			ans = v
	res.append(str(ans).encode())
os.write(1, '\n'.encode().join(res))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = [0] * 26
	for ch in s:
		count[ord(ch) - ord('a')] += 1
	count.sort()
	res = 1
	for i in range(2, n + 1):
		g = math.gcd(i, k)
		l = i // g
		ans = 0
		for x in count:
			ans += x // l
		if ans * l >= i:
			res = i
	print(res)


from math import gcd
from collections import Counter
for T in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input().strip()
	c = Counter()
	c.update(s)
	mx = 0
	for l in range(1, n + 1):
		rep = gcd(l, k)
		ans = 0
		for j in c:
			if c[j] >= l // rep:
				ans += c[j] // (l // rep)
			if ans >= rep:
				mx = l
				break
	print(mx)


import heapq

def maxheappush(x, xx):
	heapq.heapify(x)
	heapq.heappush(x, -1 * xx)

def maxheappop(x):
	heapq.heapify(x)
	ans = -1 * heapq.heappop(x)
	return ans

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc

def returncount(l):
	dic = {}
	for ss in range(len(l)):
		if l[ss] not in dic:
			dic[l[ss]] = 1
		else:
			dic[l[ss]] += 1
	val = list(dic.values())
	val = sorted(val, reverse=True)
	return val

def modlist(x, k):
	vals = []
	it = 1
	g = Graph(x)
	for i in range(x):
		g.addEdge(i, (i + k) % x)
	cc = g.connectedComponents()
	for c in cc:
		vals.append(len(c))
	vals = sorted(vals, reverse=True)
	return vals

def findfeas(b, s):
	c = []
	heapq.heapify(c)
	for bb in b:
		maxheappush(c, bb)
	ans = maxheappop(c)
	while ans >= s[0]:
		ans = ans - s[0]
		s.pop(0)
		maxheappush(c, ans)
		ans = maxheappop(c)
		if len(s) == 0:
			break
	if len(s) == 0:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	rc = returncount(s)
	for j in range(n, 0, -1):
		gg = modlist(j, k)
		if findfeas(rc, gg):
			print(j)
			break


from collections import *
import math
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	s = input()
	al = defaultdict(int)
	for i in range(len(s)):
		al[s[i]] += 1
	ans = []
	for i in al:
		ans.append(al[i])
	maxa = 0
	for i in range(1, n + 1):
		rem = k % i
		if rem == 0:
			maxa = max(maxa, i)
		else:
			q = i // math.gcd(rem, i)
			c1 = 0
			for x in range(len(ans)):
				c1 += ans[x] // q
			if c1 >= i // q:
				maxa = max(maxa, i)
	print(maxa)


import io
import os
from collections import Counter, defaultdict, deque
from bisect import bisect

def factors(n):
	fhead = []
	ftail = []
	for x in range(1, int(n ** 0.5) + 1):
		if n % x == 0:
			fhead.append(x)
			if x * x != n:
				ftail.append(n // x)
	return fhead + ftail[::-1]

def firstSmaller(arr, x):
	index = bisect(arr, x)
	if index == 0:
		return None
	return arr[index - 1]

def solve(N, K, S):
	divisors = factors(K)
	best = 1
	if N < K:
		best = firstSmaller(divisors, N)
	else:
		best = K
	freq = Counter(S)
	for repeat in range(max(freq.values()), 0, -1):
		repeatString = []
		for (k, v) in freq.items():
			repeatString.extend([k] * (v // repeat))
		trunc = firstSmaller(divisors, len(repeatString))
		best = max(best, trunc * repeat)
	return best
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	ans = solve(N, K, S)
	print(ans)


from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf():
	return [int(i) for i in get().split()]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join([str(i) for i in a]) + end)

def putff(a, sep=' ', end='\n'):
	[putf(i, sep, end) for i in a]
from collections import defaultdict as dd

def solve(n, k, s):
	d = dd(int)
	for i in s:
		d[i] += 1
	ans = 1
	for len_ in range(1, n + 1):
		k0 = 0
		for c in d:
			k0 += d[c] // len_
		for k0i in range(1, k0 + 1):
			if k % k0i == 0:
				ans = max(ans, k0i * len_)
	return ans

def main():
	q = int(get())
	for _ in range(q):
		(n, k) = getf()
		s = get()
		print(solve(n, k, s))
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = set()
	dic = {}
	for i in s:
		dic[i] = dic.get(i, 0) + 1
	a = dic.values()
	ans = 0
	for i in range(1, int(k ** 0.5) + 1):
		if k % i == 0:
			l.add(i)
			l.add(k // i)
	for fact in l:
		for j in range(fact, n + 1, fact):
			c = 0
			temp = j // fact
			for i in a:
				c += i // temp
			if c >= fact:
				ans = max(ans, j)
	print(ans)


import sys, math, cmath, time
start_time = time.time()

def solve():
	(n, k) = invr()
	s = insr()
	q = string_counter(s)
	for i in range(len(s), -1, -1):
		w = math.gcd(i, k)
		qw = i // w
		qq = 0
		for j in range(len(q)):
			if q[j] >= qw:
				qq = qq + q[j] // qw * qw
		if qq >= i:
			break
	print(i)

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	t = inp()
	for tt in range(t):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


from collections import Counter
from math import gcd
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = Counter(s)
	vals = list(c.values())
	vals.sort()
	ans = -1
	for i in range(1, n + 1):
		no_grp = gcd(i, k)
		t = i // no_grp
		cnt = 0
		for v in vals:
			v_ = v
			while v_ >= t:
				cnt += 1
				v_ -= t
		if cnt >= no_grp:
			ans = i
	print(ans)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
import random
from queue import PriorityQueue
from collections import Counter as cc
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
from itertools import permutations
from math import factorial as f

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
import sys
import sys
from math import gcd
input = sys.stdin.readline
from collections import Counter as cc
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	s = list(input().strip())
	l = cc(s)
	a = list(l.values())
	for i in range(n, 0, -1):
		g = gcd(i, k)
		p = i // g
		an = 0
		for j in a:
			if j >= p:
				an += j // p * p
		if an >= i:
			print(i)
			break


import math
from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	d = defaultdict(int)
	for i in s:
		d[i] += 1
	freq = []
	for i in d:
		freq.append(d[i])
	freq.sort(reverse=True)
	for l in range(n, 0, -1):
		if k % l == 0:
			ans = l
			break
		else:
			size_of_window = int(math.gcd(l, k))
			no_of_windows = l // size_of_window
			ele_in_one_window = 0
			for i in freq:
				ele_in_one_window += i // no_of_windows
			if ele_in_one_window >= size_of_window:
				ans = l
				break
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	f = [0] * 26
	for i in s:
		f[ord(i) - 97] += 1
	ans = 1
	for l in range(2, n + 1):
		nk = k % l
		cp = math.gcd(nk, l)
		reql = l // cp
		tmp = 0
		for i in range(0, 26):
			tmp += f[i] // reql
		if tmp * reql >= l:
			ans = l
	print(ans)


import math
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	ans = 0
	i = 1
	d = [0] * 26
	for z in s:
		d[ord(z) - ord('a')] += 1
	while i * i <= k:
		if k % i == 0:
			_i = i
			for __ in range(2):
				for x in range(1, n + 1):
					sum = 0
					for j in d:
						sum += j // x
					if sum >= _i:
						ans = max(ans, x * _i)
				_i = k // i
		i += 1
	print(ans)


t = int(input())
while t:
	(n, k) = [int(i) for i in input().split()]
	s = input()
	mem = {i: 0 for i in s}
	for c in s:
		mem[c] += 1
	chars = sorted(list(mem.values()))
	for i in range(n, 0, -1):
		p = [-1] * i
		for j in range(i):
			p[j] = (j + k) % i
		cycles = []
		unused = set([x for x in range(i)])
		while unused:
			curr = unused.pop()
			unused.add(curr)
			l = 0
			while curr in unused:
				l += 1
				unused.remove(curr)
				curr = p[curr]
			cycles.append(l)
		cycles.sort()
		x = 0
		y = 0
		char_counts = chars.copy()
		while x < len(cycles) and y < len(char_counts):
			if char_counts[y] >= cycles[x]:
				char_counts[y] -= cycles[x]
				x += 1
				if char_counts[y] != 0:
					y -= 1
			y += 1
		if x >= len(cycles):
			print(i)
			break
	t -= 1


import math
import collections
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ctr = collections.Counter(s)
	ans = 0
	for i in range(1, n + 1):
		g = math.gcd(i, k)
		l = i // g
		cnt = sum([v // l * l for v in ctr.values()])
		if cnt >= i:
			ans = i
	print(ans)


def gcd(a, b):
	return gcd(b, a % b) if b else a
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	elements = {}
	for i in s:
		if i in elements.keys():
			elements[i] += 1
		else:
			elements[i] = 1
	for i in range(n, 0, -1):
		every_nth = gcd(k, i)
		can_give = 0
		for j in elements.keys():
			can_give += elements[j] // (i // every_nth)
		if can_give >= every_nth:
			print(i)
			break


import sys
from collections import Counter
from math import gcd

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
for _ in range(INT()):
	(N, K) = MAP()
	S = input()
	C = Counter(S)
	ans = 0
	for ln in range(1, N + 1):
		cnt = 0
		x = ln // gcd(ln, K)
		for v in C.values():
			cnt += v // x * x
		if cnt >= ln:
			ans = max(ans, ln)
	print(ans)


from sys import stdin, stdout
import sys
from math import *
for __ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [0] * 26
	for i in range(n):
		a[ord(s[i]) - 97] += 1
	b = 0
	for i in range(1, k + 1):
		if k % i != 0:
			continue
		x = 1
		while True:
			l = 0
			for alpha in a:
				s = alpha // x
				l += s
			if l < i:
				break
			b = max(b, i * x)
			x += 1
	print(b)


import sys
from math import gcd
input = sys.stdin.readline
from collections import Counter as cc
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	s = list(input().strip())
	l = cc(s)
	a = list(l.values())
	for i in range(n, 0, -1):
		g = gcd(i, k)
		p = i // g
		an = 0
		for j in a:
			if j >= p:
				an += j // p * p
		if an >= i:
			print(i)
			break


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for test in range(0, t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	dic = {}
	b = []
	for i in range(0, n):
		if s[i] in dic:
			b[dic[s[i]]] += 1
		else:
			dic[s[i]] = len(b)
			b.append(1)
	kk = k
	b.sort()
	for l in range(n, 0, -1):
		k = kk % l
		if k == 0:
			print(l)
			break
		s = k * l // gcd(l, k) // k
		ll = l
		for i in range(len(b) - 1, -1, -1):
			ll -= b[i] // s * s
			if ll <= 0:
				print(l)
				break
		if ll <= 0:
			break


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)


def HOD(a, b):
	while a != 0 and b != 0:
		if a > b:
			a %= b
		else:
			b %= a
	return a + b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	d = {}
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	a = sorted(d.values())[::-1]
	for i in range(n, 0, -1):
		x = k % i
		if x == 0:
			break
		types = HOD(i, x)
		same = i // types
		c = 0
		for j in a:
			c += j // same
		if c >= types:
			break
	print(i)


import sys
from collections import defaultdict as dd
from collections import Counter as cc
from queue import Queue
import math
import itertools
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	r = sorted(list(cc(a).values()))
	for i in range(n, 0, -1):
		q = math.gcd(i, k)
		w = i // q
		z = 0
		for j in r:
			if j >= w:
				z += j // w * w
		if z >= i:
			print(i)
			break


from math import gcd
from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cou = Counter(input())
	factors = [[1] for _ in range(2001)]
	for i in range(2, 2001):
		x = i
		while x <= 2000:
			factors[x].append(i)
			x += i
	maxi = 0
	for i in range(1, n + 1):
		pe = factors[gcd(i, k)]
		ans = [0] * len(pe)
		for (j, y) in enumerate(pe):
			for x in cou:
				if cou[x] >= i // y:
					ans[j] += cou[x] // (i // y)
			if ans[j] >= y:
				maxi = i
	print(maxi)


from math import sqrt
from collections import defaultdict as dd
import sys
input = sys.stdin.readline
t = int(input())
while t:
	d = dd(int)
	(n, k) = map(int, input().split())
	s = input().split()[0]
	for i in s:
		d[i] += 1
		pre = [0] * (n + 1)
	for i in range(1, n + 1):
		for j in d:
			pre[i] += d[j] // i
	factors = []
	for i in range(1, int(sqrt(k)) + 1):
		if k % i == 0:
			factors.append(i)
			if i != k // i:
				factors.append(k // i)
	mx = 0
	for i in factors:
		for j in range(1, n + 1):
			if pre[j] >= i:
				mx = max(mx, i * j)
	print(mx)
	t -= 1


from sys import stdout, stdin
input = stdin.readline
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = [0 for i in range(26)]
	for i in s:
		a[ord(i) - 97] += 1
	x = 0
	for i in a:
		if i == n:
			x = i
			break
	if x != 0:
		stdout.write(str(n) + '\n')
		continue
	for z in range(n, -1, -1):
		q = a[:]
		visited = [0 for i in range(z)]
		cycle = []
		for i in range(z):
			if visited[i] == 0:
				j = i
				l = 0
				while visited[j] == 0:
					visited[j] = 1
					j = (j + k) % z
					l += 1
				cycle.append(l)
		flag = 0
		for i in cycle:
			flag = 0
			for j in range(26):
				if q[j] >= i:
					flag = 1
					q[j] = q[j] - i
					break
			if flag == 0:
				break
		if flag == 1:
			stdout.write(str(z) + '\n')
			break


PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

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

def fun():
	for i in vis:
		if i == -1:
			return 1
	return 0
for t in range(ii()):
	t += 1
	(n, k) = li()
	s = input()
	f = [0 for i in range(26)]
	store = []
	for i in s:
		f[ord(i) - 97] += 1
	for i in f:
		store.append(i)
	store.sort()
	store.reverse()
	ans = 1
	for i in range(2, n + 1):
		x = k % i
		if x == 0:
			ans = i
		else:
			need = i // gcd(i, x)
			cnt = 0
			for j in store:
				d = j // need
				cnt += d * need
			if cnt >= i:
				ans = i
	print(ans)


from collections import Counter
import math

def check(b, a):
	count = 0
	for i in range(len(l)):
		count += l[i] // a
	if count >= b:
		return True
	return False
for nt in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = Counter(s)
	if len(c) == 1:
		print(n)
		continue
	l = []
	for i in c:
		l.append(c[i])
	l.sort(reverse=True)
	for i in range(1, n + 1):
		if k % i == 0:
			num = i
	ans = num
	for i in range(num + 1, n + 1):
		hcf = math.gcd(i, k)
		if check(hcf, i // hcf):
			ans = i
	print(ans)


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve():
	(n, k) = rl()
	s = input()
	counts = dd(int)
	for c in s:
		counts[c] += 1
	amts = sorted(counts.values(), reverse=True)

	def check(l):
		shift = k % l
		if shift == 0:
			return True
		groups = gcd(l, shift)
		size = l // groups
		hits = 0
		for val in amts:
			if val >= size:
				hits += val // size
				if hits >= groups:
					return True
			else:
				break
		return False
	for l in range(n, 0, -1):
		if check(l):
			print(l)
			break
mode = 'T'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


import io
import os
from bisect import bisect
from collections import Counter
from math import gcd

def divisors(n):
	front = []
	back = []
	for x in range(1, int(n ** 0.5) + 1):
		if n % x == 0:
			front.append(x)
			back.append(n // x)
	if front[-1] == back[0]:
		front.pop()
	return front + back[::-1]

def firstSmaller(arr, x):
	index = bisect(arr, x)
	if index == 0:
		assert False
	assert arr[index - 1] <= x
	return arr[index - 1]

def solve(N, K, S):
	divs = divisors(K)
	freq = Counter(S)
	best = 1
	for repeat in range(max(freq.values()), 0, -1):
		pattern = []
		for (k, v) in freq.items():
			pattern.extend([k] * (v // repeat))
		trunc = firstSmaller(divs, len(pattern))
		print('pattern', pattern[:trunc] * repeat)
		best = max(best, trunc * repeat)
	return best

def solve(N, K, S):
	freq = Counter(S)
	for n in range(N, 0, -1):
		patternLen = gcd(K, n)
		repeat = n // patternLen
		possibleLen = 0
		for (k, v) in freq.items():
			possibleLen += v // repeat
		if possibleLen >= patternLen:
			return n
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	ans = solve(N, K, S)
	print(ans)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	l = [0] * 26
	for i in s:
		l[ord(i) - ord('a')] += 1
	for i in range(n, 0, -1):
		x = math.gcd(i, k)
		p = i // x
		count = 0
		for j in l:
			if j >= p:
				count += j // p * p
		if count >= i:
			print(i)
			break


from collections import Counter

def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	x = Counter(s)
	for i in range(1, n + 1):
		g = gcd(i, k)
		l = i // g
		cnt = sum([v // l * l for v in x.values()])
		if cnt >= i:
			ans = i
	print(ans)


from collections import Counter
from math import ceil, sqrt

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]
		self.extra = []

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def Union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			self.extra.append((x, y))
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		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])
		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)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
import datetime
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	starttime = datetime.datetime.now()
	tc = int(input())
	for _ in range(tc):
		(n, k) = [int(x) for x in input().split()]
		s = input()
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		sd = {k: v for (k, v) in sorted(d.items(), key=lambda item: item[1], reverse=True)}
		fa = []
		for i in sd:
			fa.append(sd[i])
		ans = 0
		for i in range(n, 0, -1):
			vis = [0] * i
			size = []
			sc = 0
			for j in range(i):
				c = 1
				t = j
				if vis[j] == 0:
					vis[j] = 1
					while True:
						if vis[(j + k) % i] == 1:
							break
						else:
							vis[(j + k) % i] = 1
							j = (j + k) % i
							c += 1
					sc += c
					size.append(c)
				j = t
				if sc >= i:
					break
			if len(set(size)) == 1:
				u = 0
				flag = 0
				z = fa[0]
				for e in size:
					if z - e < 0:
						u += 1
						if u == len(fa):
							flag = 1
							break
						z = fa[u]
					z -= e
				if flag == 0 and z >= 0:
					ans = sc
					print(ans)
					break
			if ans > 0:
				break
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import io, os
input = sys.stdin.readline
from functools import reduce

def factors(n):
	x = set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
	return list(x)

def checker(mid):
	count = []
	for i in range(n, 0, -1):
		ans = 0
		for j in alpha:
			if j >= i:
				ans += j // i
				if ans >= mid:
					return mid * i // mid * mid
	return 0
t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	s = [i for i in input() if i != '\n']
	alpha = [0] * 26
	for i in s:
		alpha[ord(i) - 97] += 1
	l = factors(k)
	ans = []
	for i in l:
		ans.append(checker(i))
	print(max(ans))


import math
t = int(input())
for _ in range(t):
	(n, k) = 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)


import sys
from collections import Counter, deque
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	cc = Counter(input())
	cc = list(sorted(cc.values(), reverse=True))
	mx = cc[0]
	for d in range(2, k + 1):
		if k % d:
			continue
		for u in range(1, n // d + 1):
			cnt = 0
			for v in cc:
				if v // u == 0:
					break
				cnt += v // u
			if cnt >= d:
				mx = max(mx, d * u)
	print(mx)


letters = 26
for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	counts = [0] * (letters + 1)
	for c in s:
		counts[ord(c) - ord('a')] += 1
	counts.sort(reverse=True)
	zeroi = counts.index(0)
	if zeroi >= 0:
		counts = counts[:zeroi]
	ans = 1
	for d in range(1, min(k, n) + 1):
		if k % d != 0:
			continue
		l = 1
		r = n // d
		while l < r:
			m = (l + r + 1) // 2
			inGroup = 0
			for count in counts:
				inGroup += count // m
			if inGroup >= d:
				l = m
			else:
				r = m - 1
		ans = max(ans, l * d)
	print(ans)


def gcd(n, k):
	if n % k == 0:
		return k
	return gcd(k, n % k)
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	s = input()
	freq = [0 for i in range(26)]
	for i in s:
		freq[ord(i) - 97] += 1
	mina = []
	for i in range(1, n + 1):
		x = gcd(i, k)
		sumi = 0
		for j in range(26):
			sumi = sumi + freq[j] // (i // x)
		if sumi >= x:
			mina.append(i)
	print(max(mina))


import collections
import string

def main():
	(n, k) = map(int, input().split())
	s = input()
	c = collections.Counter(s)
	cnt = sorted(list(c.values()))
	divs = []
	i = 1
	while i * i < k:
		if k % i == 0:
			divs.append(i)
			divs.append(k // i)
		i += 1
	if i * i == k:
		divs.append(i)
	divs.sort()
	while divs[-1] > n:
		divs.pop()
	ans = cnt[-1]
	for period in divs:
		l = 0
		r = (n + period) // period
		while l + 1 < r:
			m = (l + r) // 2
			chunks = 0
			for i in range(-min(period, len(cnt)), 0):
				chunks += cnt[i] // m
			if chunks >= period:
				l = m
			else:
				r = m
		cycles = l
		ans = max(ans, cycles * period)
	print(ans)
tn = int(input())
for _ in range(tn):
	main()


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

def feasible(n, k, beads, lng, maxcnt):
	g = gcd(k, lng)
	h = lng // g
	if g == 1:
		return lng <= maxcnt
	g0 = 0
	for (_, c) in beads.items():
		g0 += c // h
	return g <= g0

def solve(n, k, beads):
	maxcnt = 0
	for (_, c) in beads.items():
		if c > maxcnt:
			maxcnt = c
	for lng in range(n, 1, -1):
		if feasible(n, k, beads, lng, maxcnt):
			return lng
	return 1
cases = int(input().strip())
for _ in range(cases):
	(n, k) = tuple(map(int, input().strip().split()))
	store = input().strip()
	beads = {}
	for b in store:
		if b in beads:
			beads[b] += 1
		else:
			beads[b] = 1
	print(solve(n, k, beads))


from collections import Counter
import bisect
for _ in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	s = input()
	c = Counter(s)
	l = sorted([c[i] for i in c])[::-1]
	d = []
	for i in range(1, k + 1):
		if k % i == 0:
			d.append(i)
	ans = 0
	for i in d:
		for j in range(i, n + 1, i):
			c = 0
			for k in l:
				if k >= j // i:
					c += k // (j // i)
				else:
					break
			if c >= i:
				ans = max(j, ans)
			else:
				break
	print(ans)


import sys, math, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from decimal import Decimal
from fractions import Fraction

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = 10 ** 20
mod = 10 ** 9 + 7
for t in range(int(data())):
	(n, k) = mdata()
	s = data()
	d = dd(int)
	for i in range(n):
		d[s[i]] += 1
	l = sorted(d.values(), reverse=True)
	ans = 0
	div = []
	for i in range(1, int(k ** 0.5) + 1):
		if k % i == 0:
			div.append(i)
			div.append(k // i)
	for i in range(1, n + 1):
		cnt = 0
		for j in l:
			cnt += j // i
		for j in div:
			if cnt >= j:
				ans = max(ans, j * i)
	out(ans)


import heapq
from collections import Counter
from sys import stdin
input = stdin.readline
INF = 10 ** 9 + 7
MAX = 10 ** 7 + 7
MOD = 10 ** 9 + 7

def check(n, k, c):
	h = list(c)
	heapq.heapify(h)
	v = [0] * n
	for ni in range(n):
		if v[ni]:
			continue
		if not h:
			return False
		nj = ni
		(freq, char) = heapq.heappop(h)
		cnt = 0
		while not v[nj]:
			v[nj] = 1
			nj += k
			nj %= n
			cnt += 1
		if -freq > cnt:
			heapq.heappush(h, [freq + cnt, char])
		elif -freq < cnt:
			return False
	return True
for Ti in range(int(input().strip())):
	(n, k) = [int(x) for x in input().strip().split()]
	s = input().strip()
	c = [[-x[1], x[0]] for x in list(Counter(s).items())]
	for i in range(n, 0, -1):
		if check(i, k, c):
			print(i)
			break


def make_divisors(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

def main():
	q = int(input())
	for _ in range(q):
		(n, k) = map(int, input().split())
		s = input()
		while n > 0:
			if k % n == 0:
				ans = n
				break
			n -= 1
		alphabet = [0] * 26
		n = len(s)
		for i in range(n):
			alphabet[ord(s[i]) - 97] += 1
		KL = make_divisors(k)
		for nk in KL:
			ok = 0
			ng = pow(10, 18)

			def check(x, k):
				if x == 0:
					return True
				if k * x > n:
					return False
				val = 0
				for num in alphabet:
					temp = num // x * x
					val += temp
				if val >= x * k:
					return True
				else:
					return False
			while abs(ok - ng) > 1:
				mid = (ok + ng) // 2
				if check(mid, nk):
					ok = mid
				else:
					ng = mid
			ans = max(ans, ok * nk)
		print(ans)
main()


import sys
input = sys.stdin.readline
import math
import copy
import bisect
import collections
from collections import deque
import heapq
from collections import defaultdict
t = int(input())
for f in range(t):
	(n, k) = map(int, input().split())
	div = []
	for i in range(1, 2001):
		if k % i == 0:
			div.append(i)
	s = list(input().rstrip())
	c = collections.Counter(s)
	a = c.most_common()
	freq = []
	for i in a:
		freq.append(i[1])
	ans = 0
	for i in div:
		j = 1
		tmp = 0
		while j * i <= n:
			memo = 0
			for l in range(len(freq)):
				memo += freq[l] // j
			if memo >= i:
				tmp = j * i
				j += 1
			else:
				break
		ans = max(ans, tmp)
	print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = defaultdict(int)
	for i in range(n):
		d[s[i]] += 1
	d = list(d.values())
	d.sort(reverse=True)
	d1 = d + []
	for i in range(n, 0, -1):
		d = d1 + []
		graph = defaultdict(set)
		vis = [False] * (n + 1)
		req = []

		def dfs(v):
			vis[v] = True
			c = 1
			for i in graph[v]:
				if vis[i] == False:
					c += dfs(i)
			return c
		for j in range(1, i + 1):
			if (j + k) % i == j:
				continue
			if (j + k) % i == 0:
				graph[j].add((j + k) % i + i)
				graph[(j + k) % i + i].add(j)
			else:
				graph[j].add((j + k) % i)
				graph[(j + k) % i].add(j)
		for j in range(1, i + 1):
			if vis[i] == False:
				req.append(dfs(j))
		req.sort(reverse=True)
		f = 0
		t = 0
		for j in range(len(req)):
			if d[t] >= req[j]:
				d[t] -= req[j]
			else:
				f = 0
				while d[t] < req[j]:
					t += 1
					if t == len(d):
						f = 1
						break
				if f == 1:
					break
				d[t] -= req[j]
		if f == 0:
			print(i)
			break


import sys
import math
from math import factorial, inf, gcd, sqrt
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
from bisect import *
import random
sys.setrecursionlimit(10 ** 5)

def rarray():
	return [int(i) for i in input().split()]
t = 1
t = int(input())
for ii in range(t):
	(n, k) = rarray()
	s = input()
	v = sorted(Counter(s).values(), reverse=True)
	for ans in reversed(range(1, n + 1)):
		g = gcd(ans, k)
		p = ans // g
		r = 0
		cv = v.copy()
		while g > 0:
			f = True
			for (i, j) in enumerate(cv):
				if j >= p:
					cv[i] -= p
					g -= 1
					f = False
				if g == 0:
					break
			if f:
				break
		if g == 0:
			print(ans)
			break


from sys import stdin, stdout

def necklace_assembly(n, k, s):
	res = 0
	cna = [0 for i in range(26)]
	for i in range(len(s)):
		cna[ord(s[i]) - ord('a')] += 1
	for i in range(n, 0, -1):
		l = k % i
		if l == 0:
			res = i
			break
		g = gcd(i, l)
		if g != 0:
			d = 0
			need = i // g
			for v in cna:
				d += v // need * need
			if d >= i:
				res = i
				break
	return res

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(stdin.readline())
for i in range(t):
	(n, k) = list(map(int, stdin.readline().split()))
	s = stdin.readline().strip()
	stdout.write(str(necklace_assembly(n, k, s)) + '\n')


import math
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = [0] * 26
	for i in input().strip():
		a[ord(i) - ord('a')] += 1
	x = n
	while sum((i - i % (x // math.gcd(x, k)) for i in a)) < x:
		x -= 1
	print(x)


import math

def f(n):
	c = []
	d = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c.append(i)
			else:
				c.append(i)
				d.append(n // i)
		i += 1
	c += d[::-1]
	return c
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	b = f(k)
	ans = 0
	c = [0] * 26
	for j in range(n):
		c[ord(s[j]) - 97] += 1
	k = []
	for j in range(26):
		p = c[j]
		i = 1
		while p // i != 0:
			k.append(p // i)
			i += 1
	k.sort(reverse=True)
	j = 0
	r = len(k)
	while j < len(b):
		p = b[j]
		if p - 1 < r:
			ans = max(ans, p * k[p - 1])
		j += 1
	print(ans)


from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')

def solve():
	for _ in range(ii()):
		(n, k) = mi()
		s = si()
		f = [0] * 26
		for i in s:
			f[bo(i)] += 1
		ans = 0
		for i in range(1, n + 1):
			req = gcd(i, k)
			cnt = i // req
			c = 0
			for j in range(26):
				req -= f[j] // cnt
			if req <= 0:
				ans = i
		print(ans)
solve()


def solve(N, k, s):
	count = [0] * 26
	for c in s:
		count[ord(c) - 97] += 1
	ans = 0
	for n in range(1, N + 1):
		X = 0
		for c in count:
			X += c // n
		for x in range(X, 0, -1):
			if k % x == 0:
				ans = max(ans, x * n)
				break
	return ans
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = input()
	print(solve(n, k, s))


from collections import Counter
from math import gcd, floor, sqrt
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	z = sorted(list(Counter(s).values()), reverse=True)
	ma = max(z)
	an = 0
	for x in range(1, k + 1):
		if k % x == 0:
			for xx in range(1, n // x + 1):
				s = 0
				for j in range(len(z)):
					s += z[j] // xx
				if s >= x:
					an = max(x * xx, an)
	print(an)


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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	for _ in range(N()):
		(n, k) = RL()
		s = list(input())
		rec = [0] * 26
		for i in s:
			rec[ord(i) - ord('a')] += 1
		res = 1
		for d in range(1, k + 1):
			if k % d == 0:
				for l in range(d, n + 1, d):
					ct = 0
					time = l // d
					for num in rec:
						ct += num // time
					if ct >= d:
						res = max(res, l)
		print(res)
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 998244353
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def solve():
	(N, K) = getInts()
	S = getStr()
	lets = [0] * 26
	for s in S:
		lets[ord(s) - ord('a')] += 1
	lets.sort()
	facs = factors(K)
	best = 0
	for f in facs:
		curr = 1
		while True:
			tmp = [L // curr for L in lets]
			if sum(tmp) < f:
				curr -= 1
				break
			curr += 1
		best = max(best, curr * f)
	return best
for _ in range(getInt()):
	print(solve())


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	a = [0] * 26
	for i in s:
		a['abcdefghijklmnopqrstuvwxyz'.find(i)] += 1
	z = 1
	a = sorted(a)[::-1]
	a0 = list(a)
	for i in range(1, n + 1):
		b = []
		c = [0] * i
		d = 0
		for j in range(i):
			if c[j] == 0:
				d += 1
				b.append(1)
				c[j] = d
				j0 = j
				j = (j - k) % i
				while j != j0:
					b[-1] += 1
					c[j] = d
					j = (j - k) % i
		for j in b:
			for l in range(26):
				if a[l] >= j:
					a[l] -= j
					break
			else:
				break
		else:
			z = i
		a = list(a0)
	print(z)


from sys import stdout, stdin
import os, io
input = stdin.readline

def read_int():
	return map(int, input().split())

def read_list():
	return list(map(int, input().split()))

def print_list(l):
	print(' '.join(map(str, l)))
from collections import Counter

def gcd(m, n):
	while n:
		(m, n) = (n, m % n)
	return m
N = int(input())
for _ in range(N):
	(n, k) = read_int()
	bead = input().strip()
	dic = Counter(bead)
	for i in range(n, 0, -1):
		target = gcd(i, k)
		m = i // target
		tmp = 0
		for d in dic.values():
			tmp += d // m
			if tmp >= target:
				break
		if tmp >= target:
			print(i)
			break


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from collections import Counter
	from math import gcd
	t = int(input())
	ans_a = [0] * t
	for ti in range(t):
		(n, k) = map(int, input().split())
		char_cnt = list(Counter(input().rstrip()).values())
		if k == 0:
			ans_a[ti] = n
			continue
		for i in range(n, 0, -1):
			group = gcd(k, i)
			cnt = i // group
			if sum((x // cnt for x in char_cnt)) >= group:
				ans_a[ti] = i
				break
	sys.stdout.buffer.write(('\n'.join(map(str, ans_a)) + '\n').encode('utf-8'))
main()


import sys
import math
import collections
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(N, K) = [int(x) for x in input().split()]
		S = input().strip()
		c = collections.Counter(S)
		for i in range(N + 1, -1, -1):
			ik_gcd = math.gcd(i, K)
			x = i // ik_gcd
			tmpcnt = 0
			for k in c.keys():
				tmpcnt += c[k] // x
			if tmpcnt >= ik_gcd:
				print(i)
				break
main()


import sys
import math as mt

def divisors(n):
	l = []
	i = 1
	while i <= mt.sqrt(n):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
		i = i + 1
	return l
t = int(input())
for __ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = [0] * 27
	for i in range(len(s)):
		l[ord(s[i]) - 97] += 1
	l.sort()
	maxi = 1
	for i in range(n, 0, -1):
		l1 = divisors(i)
		for j in l1:
			g = mt.gcd(j, k)
			ch = 0
			same = i // g
			cnt = 0
			for i1 in range(len(l)):
				if l[i1] >= same:
					cnt += l[i1] // same
			if cnt >= g:
				maxi = max(maxi, i)
	print(maxi)


from math import gcd
from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cou = Counter(input())
	maxi = 0
	for i in range(1, n + 1):
		pe = gcd(i, k)
		ans = 0
		for x in cou:
			if cou[x] >= i // pe:
				ans += cou[x] // (i // pe)
		if ans >= pe:
			maxi = i
	print(maxi)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	cc = [v for (_, v) in Counter(s).items()]
	cc.sort()
	mx = 0
	for subk in range(1, k + 1):
		if k % subk != 0:
			continue
		for l in range(1, n + 1):
			local = sum(map(lambda x: x // l, cc))
			if local >= subk:
				mx = max(mx, subk * l)
	print(mx)


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]
					elif 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())


from collections import Counter
from math import gcd

def solve(s: str, k: int) -> int:
	c = Counter(s).values()
	best = 0
	for length in range(1, len(s) + 1):
		period = gcd(length, k)
		min_count = length // period
		current = 0
		for v in c:
			current += v // min_count
			if current >= period:
				best = length
				break
	return best
tc = int(input())
while tc > 0:
	(n, k) = map(int, input().split())
	print(solve(input(), k))
	tc -= 1


from collections import Counter
from collections import defaultdict
from collections import deque
import math
import heapq
import sys
import io, os
input = sys.stdin.readline
from bisect import *
rs = lambda : input().strip()
ri = lambda : int(input())
rl = lambda : list(map(int, input().strip().split()))
rls = lambda : list(map(str, input().split()))
t = int(input())
for _ in range(0, t):
	(n, k) = rl()
	s = input()
	d = Counter(s)
	v = list(d.values())
	x1 = sorted(v, reverse=True)
	v.sort(reverse=True)
	for i in range(n, 0, -1):
		vis = [0] * i
		l = []
		for j in range(0, i):
			if vis[j] == 1:
				continue
			c = j
			a = 0
			while 1:
				if vis[c] == 1:
					l.append(a)
					break
				vis[c] = 1
				a = a + 1
				c = (c + k) % i
		p = 0
		f = 1
		v = x1.copy()
		for j in l:
			while 1:
				if p == len(v):
					f = 0
					break
				if v[p] >= j:
					v[p] = v[p] - j
					break
				else:
					p = p + 1
		if f == 1:
			print(i)
			break


import atexit
import io
import sys
import math
from collections import defaultdict, Counter
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if k % n == 0:
		print(n)
		continue
	c2 = list(Counter(s).values())
	for j in range(n, 0, -1):
		c = c2[:]
		d = defaultdict(list)
		for kk in range(j):
			d[kk] = (kk + k) % j
		visit = [0] * j
		l = []
		for kk in range(j):
			if visit[kk] == 0:
				c1 = 1
				visit[kk] = 1
				p = d[kk]
				while visit[p] == 0:
					c1 += 1
					visit[p] = 1
					p = d[p]
				l.append(c1)
		l.sort(reverse=True)
		for kk in l:
			m = max(c)
			if m >= kk:
				ind = c.index(m)
				c[ind] -= kk
			else:
				break
		else:
			print(j)
			break


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = input()
		d = {}
		M = 0
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			M = max(M, d[i])
		s = sorted(d.keys(), key=lambda x: d[x], reverse=True)
		qs = [k]
		for j in range(2, int(k ** 0.5) + 2):
			if k % j == 0:
				qs.append(j)
				qs.append(k // j)
		L = M
		for q in qs:
			max_reps = n // q
			for reps in range(max_reps, 0, -1):
				total_contribs = 0
				for potential_contributor in s:
					given_contrib = d[potential_contributor] // reps
					if given_contrib == 0:
						break
					total_contribs += given_contrib
				if total_contribs < q:
					continue
				L = max(L, q * reps)
				break
		print(L)
main()


import math

def factors(a):
	i = 1
	x = math.sqrt(a)
	lis = []
	while i <= x:
		if a % i == 0:
			if i == x:
				lis.append(i)
			else:
				lis.append(i)
				lis.append(a // i)
		i += 1
	lis.sort()
	return lis
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = str(input())
	array = factors(k)
	lis = [0] * 26
	for j in range(n):
		lis[ord(s[j]) - 97] += 1
	arr = []
	for j in range(26):
		if lis[j] > 0:
			arr.append(lis[j])
	ans = 0
	for j in array:
		l = j
		while l <= n:
			s = 0
			x = l // j
			for m in arr:
				s += m // x
			if s >= j:
				ans = max(ans, l)
			l += j
	print(ans)


import collections
import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	cnt = list((i for (j, i) in collections.Counter(s).items()))
	for i in range(n, 0, -1):
		l = math.gcd(k, i)
		r = i // l
		for j in cnt:
			l -= j // r
		if l <= 0:
			break
	print(i)


from math import gcd
from sys import stdin, gettrace
from collections import Counter
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():

	def solve(n, k, ss):
		(_, counts) = zip(*Counter(ss).most_common())
		for i in range(n, 0, -1):
			if k % i == 0:
				return i
			j = gcd(k, i)
			l = i // j
			found = 0
			for c in counts[0:j]:
				found += c // l
			if found >= j:
				return i
	t = int(inputi())
	for _ in range(t):
		(n, k) = map(int, input().split())
		ss = list(input())
		print(solve(n, k, ss))
main()


import sys
input = sys.stdin.readline
RI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : input().strip().split()
from collections import defaultdict as df
t = int(input().strip())
for _ in range(t):
	(n, k) = RI()
	s = input().strip()
	d = df(int)
	for i in s:
		d[i] += 1
	for i in range(n, 0, -1):
		cycles = []
		done = [0] * i
		cur = 0
		for j in range(i):
			if done[j] == 1:
				continue
			else:
				cur = 1
				done[j] = 1
				m = (j + k) % i
				while done[m] == 0:
					cur += 1
					done[m] = 1
					m = (m + k) % i
				cycles.append(cur)
				cur = 0
		cycles.sort(reverse=True)
		cpy = d.copy()
		f = 0
		for j in cycles:
			f = 0
			for m in cpy:
				if cpy[m] >= j:
					cpy[m] -= j
					f = 1
					break
			if f == 0:
				break
		if f == 0:
			continue
		else:
			print(i)
			break


from heapq import *

def root(parent, child):
	while parent[child] != -1:
		child = parent[child]
	return child

def union(parent, size, a, b):
	(root_a, root_b) = (root(parent, a), root(parent, b))
	if root_a == root_b:
		return 0
	elif size[root_a] > size[root_b]:
		parent[root_b] = root_a
		size[root_a] += size[root_b]
		return 1
	else:
		parent[root_a] = root_b
		size[root_b] += size[root_a]
		return 1

def check(cnts, k, length):
	if k % length == 0:
		return True
	parent = [-1 for i in range(length)]
	size = [1 for i in range(length)]
	for i in range(length):
		union(parent, size, i, (i + k) % length)
	heap = [-i for i in cnts if i != 0]
	heapify(heap)
	for i in range(length):
		if parent[i] == -1:
			temp = -heappop(heap)
			if temp < size[i]:
				return False
			else:
				heappush(heap, size[i] - temp)
	return True
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	cnts = [0 for i in range(26)]
	for i in s:
		cnts[ord(i) - 97] += 1
	cnts.sort(reverse=True)
	for length in range(n, 0, -1):
		if check(cnts, k, length):
			print(length)
			break


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
cnt = []
k1 = k = 0

def ispos(m):
	global cnt, k, k1
	k = k1
	k = k % m
	if not k:
		return 1
	else:
		req = m // math.gcd(m, k)
		tot = 0
		for i in cnt:
			tot += cnt[i] // req
		return 1 if tot * req >= m else 0
for _ in range(val()):
	(n, k) = li()
	k1 = k
	cnt = Counter(st())
	ans = 0
	for i in range(min(n, 2000)):
		if ispos(i + 1):
			ans = i + 1
	print(ans)


def ans(x):
	print(x)

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	alphcnt = [0] * 26
	for i in s:
		alphcnt[ord(i) - 97] += 1
	alphcnt.sort(reverse=True)
	end = 1
	for i in range(n, -1, -1):
		g = gcd(i, k)
		if g == 1:
			if alphcnt[0] >= i:
				ans(i)
				end = 0
		else:
			cnt = 0
			p = i // g
			for j in alphcnt:
				cnt += j // p
			if cnt >= g:
				ans(i)
				end = 0
		if end == 0:
			break


import sys
from math import gcd
from bisect import bisect_left as br
from collections import Counter as CO
from collections import defaultdict as dd
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, kk) = map(int, input().split())
	word = list(map(str, input().strip()))
	df = dd(int)
	fact = []
	for k in word:
		df[k] += 1
	ans = 0
	for i in range(1, n + 1):
		maxi = 0
		x = 0
		co = 0
		for j in df:
			if df[j] // i != 0:
				maxi += df[j] // i
		if maxi == 0:
			break
		for j in range(maxi, 0, -1):
			if kk % j == 0:
				maxi = j
				break
		ans = max(ans, maxi * i)
	print(ans)


def binary_search(item, start, end, l):
	if start > end:
		return max(end, 0)
	if start > len(l) - 1:
		return len(l) - 1
	mid = (start + end) // 2
	if l[mid] > item:
		return binary_search(item, start, mid - 1, l)
	elif l[mid] < item:
		return binary_search(item, mid + 1, end, l)
	else:
		return mid

def f():
	(n, k) = map(int, input().split(' '))
	multiplesofk = []
	for i in range(1, k + 1):
		if k % i == 0:
			multiplesofk.append(i)
	string = input()
	counter = [0] * 200
	for i in range(0, len(string)):
		counter[ord(string[i])] += 1
	listofcount = []
	for i in range(ord('a'), ord('z') + 1):
		if counter[i] != 0:
			listofcount.append(counter[i])
	maximum = 0
	for i in range(1, max(listofcount) + 1):
		s = 0
		for j in range(0, len(listofcount)):
			s += listofcount[j] // i
		element = binary_search(s, 0, len(multiplesofk) - 1, multiplesofk)
		maximum = max(maximum, multiplesofk[element] * i)
	print(maximum)
for i in range(int(input())):
	f()


from collections import Counter

def calc_factors(N):
	i = 1
	factors = set()
	while i * i <= N:
		if N % i == 0:
			factors.add(i)
			factors.add(N // i)
		i += 1
	return list(sorted(factors))
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	L = input()
	C = Counter(L)
	C = list(sorted(Counter(L).values()))
	ans = 0
	factors_k = calc_factors(K)
	for fac in factors_k:
		max_val = 0
		for i in range(1, C[-1] + 1):
			cnt = 0
			idx = 0
			while idx < len(C):
				r = C[idx] // i
				cnt += r
				idx += 1
			if cnt >= fac:
				max_val = max(max_val, i)
		ans = max(ans, fac * max_val)
	print(ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return (flag, prime)

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

@bootstrap
def dfs(r):
	vis[r] = 1
	ans[r - 1] = val[r]
	for ch in g[r]:
		if d[ch] > d[r]:
			yield dfs(ch)
			ans[r - 1] = min(ans[r - 1], ans[ch - 1])
	yield None

def f(x, g):
	ans = 0
	for ch in res:
		ans += c[ch] // x
	return ans >= g
t = N()
for i in range(t):
	(n, k) = RL()
	s = input()
	c = Counter(s)
	res = sorted(c.keys(), reverse=True)
	m = k
	for i in range(n, 0, -1):
		k = m % i
		if k == 0:
			ans = i
			break
		g = gcd(k, i)
		a = i // g
		if f(a, g):
			ans = i
			break
	print(ans)


from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))

def solve():
	(n, k) = get_tuple()
	st = input()
	freq_dic = Counter(st)
	max_group_size = max(freq_dic.values())
	ans = 0
	for group_size in range(max_group_size, 0, -1):
		group_length = 0
		for val in freq_dic.values():
			group_length += val // group_size
		while k % group_length != 0 and group_length > 0:
			group_length -= 1
		ans = max(ans, group_length * group_size)
	return ans

def main():
	print(solve())
TestCases = True
if TestCases:
	for i in range(get_int()):
		main()
else:
	main()


import collections
T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	arr = input()
	dic = collections.defaultdict(int)
	for i in range(n):
		dic[arr[i]] += 1
	parts = []
	for key in dic:
		parts.append(dic[key])
	if n == k:
		print(n)
	elif n > k:
		res = k
		for l in range(k + 1, n + 1):
			start = 1
			cur = (1 + k) % l
			count = 1
			while cur != start:
				count += 1
				cur = (cur + k) % l
			have = 0
			for part in parts:
				have += part // count
			if have * count >= l:
				res = l
		print(res)
	else:
		res = 1
		for l in range(2, n + 1):
			if k % l == 0:
				res = l
			else:
				temp = k % l
				start = 1
				cur = (1 + temp) % l
				count = 1
				while cur != start:
					count += 1
					cur = (cur + temp) % l
				have = 0
				for part in parts:
					have += part // count
				if have * count >= l:
					res = l
		print(res)
	T -= 1


from collections import Counter
import sys
from math import ceil
input = sys.stdin.readline

def prog():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input().strip()
		amounts = Counter(s)
		most = list(amounts.values())
		most.sort(reverse=True)
		diff = len(most)
		beauties = []
		for i in range(1, min(int(k ** 0.5 + 1), n + 1)):
			if k % i == 0:
				if i <= n:
					beauties.append(i)
				if k // i <= n:
					beauties.append(k // i)
		lengths = []
		for beauty in beauties:
			l = 1
			r = n // beauty
			while l != r:
				m = ceil((l + r) / 2)
				need = beauty
				idx = 0
				while need > 0 and idx < diff and (most[idx] >= m):
					need -= most[idx] // m
					idx += 1
				if need <= 0:
					l = m
				else:
					r = m - 1
			lengths.append(l * beauty)
		print(max(lengths))
prog()


import math
nb_cases = int(input())
while nb_cases > 0:
	nb_cases -= 1
	(n, k) = [int(x) for x in input().split()]
	s = input()
	nb_letters = [0] * 26
	for pos in range(n):
		nb_letters[ord(s[pos]) - 97] += 1
	min_val = 0
	for x in range(1, n + 1):
		y = x / max(1, math.gcd(k % x, x))
		new_letters = [int(nb_letter / y) for nb_letter in nb_letters]
		nb = sum(new_letters)
		if nb * y >= x:
			min_val = x
	print(min_val)