You have a string $s$ consisting of lowercase Latin alphabet letters.

You can color some letters in colors from $1$ to $k$. It is not necessary to paint all the letters. But for each color, there must be a letter painted in that color.

Then you can swap any two symbols painted in the same color as many times as you want.

After that, $k$ strings will be created, $i$-th of them will contain all the characters colored in the color $i$, written in the order of their sequence in the string $s$.

Your task is to color the characters of the string so that all the resulting $k$ strings are palindromes, and the length of the shortest of these $k$ strings is as large as possible.

Read the note for the first test case of the example if you need a clarification.

Recall that a string is a palindrome if it reads the same way both from left to right and from right to left. For example, the strings abacaba, cccc, z and dxd are palindromes, but the strings abab and aaabaa — are not.


-----Input-----

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input data sets in the test.

The descriptions of the input data sets follow.

The first line of the description of each input data set contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string and the number of colors in which its letters can be painted. The second line of the description of each input data set contains a string $s$ of length $n$ consisting of lowercase letters of the Latin alphabet.

It is guaranteed that the sum of n over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each set of input data, output a single integer  — the maximum length of the shortest palindrome string that can be obtained.


-----Examples-----

Input
10
8 2
bxyaxzay
6 3
aaaaaa
6 1
abcdef
6 6
abcdef
3 2
dxd
11 2
abcabcabcac
6 6
sipkic
7 2
eatoohd
3 1
llw
6 2
bfvfbv
Output
3
2
1
1
1
5
1
1
3
3


-----Note-----

In the first test case, $s$="bxyaxzay", $k=2$. We use indices in the string from $1$ to $8$. The following coloring will work: $\mathtt{\mathbf{{b}\color{blue}{xy}{a}\color{blue}{x}z{a}\color{blue}{y}}}$ (the letter z remained uncolored). After painting:

swap two red characters (with the indices $1$ and $4$), we get $\mathtt{\mathbf{{a}\color{blue}{xy}{b}\color{blue}{x}z{a}\color{blue}{y}}}$;

swap two blue characters (with the indices $5$ and $8$), we get $\mathtt{\mathbf{{a}\color{blue}{xy}{b}\color{blue}{y}z{a}\color{blue}{x}}}$.

Now, for each of the two colors we write out the corresponding characters from left to right, we get two strings $\mathtt{\mathbf{{aba}}}$ and $\mathtt{\mathbf{\color{blue}{xyyx}}}$. Both of them are palindromes, the length of the shortest is $3$. It can be shown that the greatest length of the shortest palindrome cannot be achieved.

In the second set of input data, the following coloring is suitable: $[1, 1, 2, 2, 3, 3]$. There is no need to swap characters. Both received strings are equal to aa, they are palindromes and their length is $2$.

In the third set of input data, you can color any character and take it into a string.

In the fourth set of input data, you can color the $i$th character in the color $i$.

In the fifth set of input data can be colored in each of the colors of one character.

In the sixth set of input data, the following coloring is suitable: $[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]$. Rearrange the characters so as to get the palindromes abcba and acbca.

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	d = dict()
	for i in inp():
		d[i] = d.get(i, 0) + 1
	del d['\n']
	pairs = 0
	for i in d:
		pairs += d[i] // 2
	pk = pairs // k
	if n - pk * 2 * k >= k:
		print(pk * 2 + 1)
	else:
		print(pk * 2)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input().strip()
	mp = {}
	for i in s:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	x = 0
	for i in mp.values():
		x += i // 2
	ans = x // k * 2
	rem = n - ans * k
	if rem >= k:
		ans += 1
	print(ans)
	t -= 1


cases = int(input())
finalstring = ''
for case in range(cases):
	numbers = [int(x) for x in input().split(' ')]
	givenstring = input()
	finalvalue = 1
	myDict = {}
	for char in givenstring:
		myDict.setdefault(char, 0)
		myDict[char] += 1
	duplicate = 0
	nonduplicate = 0
	for (key, value) in myDict.items():
		if value % 2 == 0:
			duplicate += value
		else:
			duplicate += value - 1
			nonduplicate += 1
	shortmax = numbers[0] // numbers[1]
	while shortmax > 1:
		if shortmax % 2 != 0:
			unique = numbers[1] if nonduplicate >= numbers[1] else nonduplicate
			if shortmax * numbers[1] <= duplicate + unique:
				finalvalue = shortmax
				break
			else:
				shortmax -= 1
		elif shortmax * numbers[1] <= duplicate:
			finalvalue = shortmax
			break
		else:
			shortmax -= 1
	finalstring += f'{finalvalue}\n'
print(finalstring)


from functools import lru_cache as cache
from collections import Counter
import math
from heapq import *
import sys

def get_int():
	return int(input())

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

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

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

def main():
	testcases = get_int()
	for i in range(testcases):
		(n, k) = get_ints()
		s = get_string()
		print(solve(s, k, n))

def solve(s, k, n):
	start = 1
	end = n // k
	count = Counter(s)
	pairs = 0
	ones = 0
	for letter in count.keys():
		if count[letter] % 2 == 0:
			pairs += count[letter] // 2
		else:
			pairs += count[letter] // 2
			ones += 1
	while start < end:
		mid = start + math.ceil((end - start + 1) / 2)
		current_ones = ones
		current_pairs = pairs
		invalid = False
		for i in range(k):
			current_pairs -= mid // 2
			if mid % 2 == 1:
				if current_ones > 0:
					current_ones -= 1
				else:
					current_ones += 1
					current_pairs -= 1
			if current_pairs < 0:
				invalid = True
				break
		if invalid:
			end = mid - 1
		else:
			start = mid
	return start
main()


def coloring(s, k):
	pairs = 0
	paired = {'a': True, 'b': True, 'c': True, 'd': True, 'e': True, 'f': True, 'g': True, 'h': True, 'i': True, 'j': True, 'k': True, 'l': True, 'm': True, 'n': True, 'o': True, 'p': True, 'q': True, 'r': True, 's': True, 't': True, 'u': True, 'v': True, 'w': True, 'x': True, 'y': True, 'z': True}
	for alph in s:
		if paired[alph]:
			paired[alph] = False
		else:
			paired[alph] = True
			pairs += 1
	single = tuple(paired.values()).count(False) + 2 * (pairs % k)
	if single >= k:
		return 1 + 2 * (pairs // k)
	else:
		return 2 * (pairs // k)
t = int(input())
tests = [0 for i in range(t)]
n = 0
k = 0
for i in range(t):
	(n, k) = map(int, input().split())
	tests[i] = coloring(input(), k)
for test in tests:
	print(test)


import sys
sys.setrecursionlimit(10 ** 8)
t = int(input())
for _ in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	s = sys.stdin.readline().rstrip()
	su = 0
	ans = 0
	alpha = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
	for i in s:
		alpha[i] += 1
	for i in alpha.keys():
		if alpha[i] >= 2:
			su = su + alpha[i] // 2
	ans = su // k * 2
	if su % k * 2 + n - su * 2 >= k:
		ans += 1
	print(ans)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

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

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = int_arr()
	st = input()
	cnt = 0
	d = dict()
	rem = 0
	for i in st:
		d[i] = d.get(i, 0) + 1
	for i in d.values():
		if i % 2 != 0:
			cnt += i - 1
			rem += 1
		else:
			cnt += i
	ans = cnt // k
	rem += cnt % k
	if ans % 2 == 0:
		if rem // k > 0:
			print(ans + 1)
		else:
			print(max(ans, 1))
	else:
		print(max(ans, 1))


import math
from os import remove

def test():
	(n, k) = map(int, input().split())
	pairs = 0
	st = []
	ch = input()
	for i in range(n):
		if ch[i] in st:
			st.remove(ch[i])
			pairs += 1
		else:
			st.append(ch[i])
	ones = len(st)
	minlen = pairs // k * 2
	if pairs % k * 2 + ones >= k:
		minlen += 1
	print(int(minlen))
t = int(input())
for i in range(t):
	test()


for l in range(int(input())):
	(n, k) = list(map(int, input().split()))
	st = input()
	dic = {i: 0 for i in st}
	for i in st:
		dic[i] += 1
	ts = 0
	for i in dic:
		ts += dic[i] // 2
	ans = 2 * (ts // k)
	if n - ans * k >= k:
		ans += 1
	print(ans)


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	letters = [0] * 26
	for c in s:
		letters[ord(c) - 97] += 1
	num_evens = 0
	for x in letters:
		num_evens += x // 2
	r = n // k + 1
	l = 1
	cur = (l + r) // 2
	while r - l > 1:
		if cur // 2 * k <= num_evens:
			l = cur
		else:
			r = cur
		cur = (l + r) // 2
	print(cur)


import sys
from collections import Counter

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

def read_ints_line():
	return [int(x) for x in read_line().split()]
t = int(read_line())
for _ in range(t):
	(n, k) = tuple(read_ints_line())
	s = [ord(x) - ord('a') for x in read_line()]
	cnt = Counter(s)
	cnt_uneven = len([x for x in cnt.values() if x % 2 == 1])
	even_len = (n - cnt_uneven) // k
	even_len -= even_len % 2
	extra = n - even_len * k
	max_len = even_len + int(extra >= k)
	print(max_len)


def solve():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = input()
		mp = {}
		for ele in a:
			mp[ele] = mp.get(ele, 0) + 1
		pair = 0
		for key in mp:
			pair += mp[key] // 2
		left = len(a) - pair * 2
		ans = 2 * (pair // k)
		left += pair % k * 2
		if left >= k:
			print(ans + 1)
		else:
			print(ans)
solve()


def solve():
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	for c in s:
		d[c] = d.get(c, 0) + 1
	pairs = 0
	for v in d.values():
		pairs += v // 2
	sz = pairs // k * 2
	rem = n - pairs // k * k * 2
	if rem >= k:
		print(sz + 1)
	else:
		print(sz)
t = int(input())
for _ in range(t):
	solve()


def solve():
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for x in s:
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	pair = 0
	ones = 0
	for x in d:
		pair += d[x] // 2
		d[x] = d[x] % 2
		ones += d[x]
	ans = pair // k * 2
	ones += pair % k * 2
	if ones >= k:
		ans += 1
	return ans
t = int(input())
for i in range(t):
	print(solve())


def solve():
	(n, k) = list(map(int, input().split()))
	s = input()
	cnt = {i: 0 for i in s}
	for i in s:
		cnt[i] += 1
	ts = 0
	for i in cnt:
		ts += cnt[i] // 2
	ans = 2 * (ts // k)
	if n - ans * k >= k:
		ans += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	sets = list(set(s))
	val = 0
	for i in sets:
		val += s.count(i) // 2
	indi = n - val * 2
	ans = 0
	while val >= k:
		ans += 2
		val -= k
	if val * 2 + indi >= k:
		ans += 1
	print(ans)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k) = map(int, input().split())
	a = input()
	dict = {}
	for i in range(n):
		if a[i] not in dict:
			dict[a[i]] = 1
		else:
			dict[a[i]] += 1
	pair = 0
	odd = 0
	for element in dict:
		pair += dict[element] // 2
		odd += dict[element] % 2
	odd += 2 * (pair % k)
	ans = pair // k * 2 + (odd >= k)
	print(ans)
q = 1
q = int(input())
for i in range(q):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	s = input()
	d = {}
	for x in s:
		d[x] = d.get(x, 0) + 1
	count = 0
	left = set()
	for i in d:
		if d[i] % 2 == 0:
			count += d[i]
		else:
			count += d[i] - 1
			left.add(i)
	ans = count // k
	if len(left) < k - count % k or ans % 2 == 1:
		print(ans)
	else:
		print(ans + 1)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	if n < 2 * k:
		print(1)
	else:
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = list(d.values())
		pairs = 0
		for i in l:
			pairs = pairs + i // 2
		ans = pairs // k * 2
		left1 = n - ans * k
		if left1 >= k:
			ans += 1
		print(ans)


def palindromesColoring(n, k, s):
	if k == n:
		return 1
	s = list(s)
	d = {}
	for x in s:
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	a = 0
	b = 0
	for x in d:
		if d[x] % 2 == 0:
			a += d[x] // 2
		else:
			a += d[x] // 2
			b += 1
	c = a // k
	r = k - a % k
	if b >= r:
		return 2 * c + 1
	elif k - r + b >= r:
		return 2 * c + 1
	else:
		return 2 * c
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(palindromesColoring(n, k, s))


def solve():
	(n, k) = map(int, input().split())
	s = input()
	cnt = {}
	for i in s:
		if i in cnt.keys():
			cnt[i] += 1
		else:
			cnt[i] = 1
	odd_cnt = even_cnt = 0
	for (i, j) in cnt.items():
		even_cnt += j // 2
		odd_cnt += j % 2
	ans = 2 * (even_cnt // k)
	remaining = even_cnt % k
	odd_cnt += remaining * 2
	if odd_cnt >= k:
		ans += 1
	print(ans)
for _ in range(int(input())):
	solve()


test = int(input())
while test:
	test -= 1
	(n, k) = [int(x) for x in input().split()]
	s = input()
	pair = 0
	single = 0
	d = {}
	for c in s:
		if c in d:
			d[c] += 1
		else:
			d[c] = 1
	for c in d:
		pair += d[c] // 2
		single += d[c] % 2
	single += pair % k * 2
	l = pair // k * 2
	if single >= k:
		print(l + 1)
	else:
		print(l)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	dic = {}
	for j in range(len(s)):
		if s[j] in dic:
			dic[s[j]] += 1
		else:
			dic[s[j]] = 1
	pairs = 0
	singles = 0
	for i in dic.values():
		pairs += i // 2
		singles += i % 2
	ll = pairs // k
	singles += pairs % k * 2
	ll = ll * 2
	if singles >= k:
		ll += 1
	print(ll)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	h = {}
	for i in s:
		h[i] = h.get(i, 0) + 1
	pairs = 0
	singles = 0
	for i in h:
		pairs += h[i] // 2
		singles += h[i] & 1
	if pairs < k:
		print(1)
		continue
	minl = 2 * (pairs // k)
	singles += 2 * (pairs % k)
	if singles >= k:
		minl += 1
	print(minl)


N = int(input())
for i in range(N):
	(n, k) = map(int, input().split())
	s = input()
	dick1 = {}
	for el in s:
		dick1[el] = dick1.get(el, 0) + 1
	pairs_num = 0
	free_guys = 0
	for el in dick1:
		pairs_num += dick1[el] // 2
		free_guys += dick1[el] % 2
	min_num = n // k
	while min_num > 1:
		if min_num // 2 * k <= pairs_num and min_num % 2 * k <= free_guys + (pairs_num - min_num // 2 * k) * 2:
			break
		min_num -= 1
	print(min_num)


n = int(input())
for i in range(n):
	(n, k) = map(int, input().split())
	para = 0
	a = []
	str = input()
	for i in range(n):
		if str[i] in a:
			a.remove(str[i])
			para += 1
		else:
			a.append(str[i])
	one = len(a)
	len_min = para // k * 2
	if para % k * 2 + one >= k:
		len_min += 1
	print(len_min)


import sys
from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	h = {}
	for i in s:
		if i not in h:
			h[i] = 1
		else:
			h[i] += 1
	p = 0
	e = 0
	for i in h:
		p += h[i] // 2
		e += h[i] % 2
	e += p % k * 2
	m = 1 if e >= k else 0
	print(p // k * 2 + m)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	counter_2 = 0
	for i in d:
		counter_2 += d[i] // 2
	ans = counter_2 // k * 2
	extra = n - ans * k
	ans += 1 if extra >= k else 0
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = list(input())
	s.sort()
	unique = set(s)
	dct = dict()
	for i in unique:
		dct[i] = s.count(i)
	pairs = 0
	singles = 0
	for i in dct:
		pairs += dct[i] // 2
		singles += dct[i] % 2
	if k > pairs:
		print(1)
		continue
	shortest = 0
	while pairs >= k:
		shortest += 2
		pairs -= k
	singles += pairs * 2
	if singles >= k:
		shortest += 1
	print(shortest)


from collections import Counter

def solve(string, k):
	counts = Counter(string)
	num_pairs = 0
	num_singles = 0
	for (char, count) in counts.items():
		num_pairs += count // 2
		num_singles += count % 2
	ans = 2 * (num_pairs // k)
	num_singles += 2 * (num_pairs % k)
	if num_singles >= k:
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	(_, k) = input().split()
	s = input()
	print(solve(s, int(k)))


t = int(input())
while t:
	l = []
	(n, k) = map(int, input().split())
	s = input()
	for ele in s:
		if ele not in l:
			l.append(ele)
	cp = 0
	for ele in l:
		cp += s.count(ele) // 2
	if len(s) - k * 2 * (cp // k) >= k:
		ans = 2 * (cp // k) + 1
	else:
		ans = 2 * (cp // k)
	print(ans)
	t -= 1


from collections import Counter

def check(n, k, s):
	data = dict(Counter(s))
	(total1, total2) = (0, 0)
	for i in data.values():
		sharma = i // 2
		total2 += sharma
		total1 += i - sharma * 2
	val = total2 // k
	ans = val * 2
	re = total2 - val * k
	total1 += re * 2
	if total1 >= k:
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(check(n, k, s))


_ = int(input())
for __ in range(_):
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		print(1)
		continue
	letters = {}
	pairs = 0
	for l in s:
		if l not in letters:
			letters[l] = 1
		else:
			letters[l] += 1
	for x in letters:
		pairs += letters[x] // 2
	if k > pairs:
		print(1)
		continue
	used_pairs = pairs // k
	single = n - pairs * 2 + (pairs * 2 - used_pairs * k * 2)
	if single >= k:
		print(used_pairs * 2 + 1)
	else:
		print(used_pairs * 2)


from collections import Counter

def solve():
	(n, k) = [int(x) for x in input().split()]
	s = input()
	res = 0
	cnts = Counter(s)
	pairs = 0
	for pc in cnts.values():
		pairs += pc // 2
	res = 2 * (pairs // k)
	if n - res * k >= k:
		res += 1
	return res
t = int(input())
for _ in range(t):
	print(solve())


from collections import Counter
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	Q = Counter(s)
	p = sum((i // 2 for i in Q.values()))
	ans = p // k * 2
	if n - ans * k >= k:
		ans += 1
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = {}
	for i in range(n):
		if s[i] in cnt:
			cnt[s[i]] += 1
		else:
			cnt[s[i]] = 1
	pairs = 0
	odd = 0
	for i in cnt:
		if cnt[i] % 2:
			odd += 1
		pairs += cnt[i] // 2
	ans = 2 * (pairs // k)
	odd += 2 * (pairs % k)
	if odd >= k:
		ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = dict()
	for c in s:
		cnt[c] = cnt.get(c, 0) + 1
	(even, odd) = (0, 0)
	for c in cnt:
		isOdd = cnt[c] % 2
		odd += isOdd
		even += cnt[c] - isOdd
	d = even // k
	if d == 0:
		print(1)
		continue
	isEven = d % 2 == 0
	remainder = d != even / k
	ans = -1
	if not remainder and isEven:
		ans = d + (odd >= k)
		print(ans)
		continue
	if not remainder and (not isEven):
		ans = d
		print(ans)
		continue
	if remainder and (not isEven):
		ans = d
		print(ans)
		continue
	if remainder and isEven:
		ans = d
		rem = even - d * k
		odd += rem
		ans += odd >= k
		print(ans)
		continue


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = list(input())
	if n == k:
		print(1)
	else:
		dic = {}
		for i in string:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		count = 0
		for i in dic:
			if dic[i] % 2 == 1:
				count += 1
		temp = int((n - count) / 2)
		if temp < k:
			print(1)
		else:
			count += temp % k * 2
			re = temp // k * 2
			if count >= k:
				re += 1
			print(re)


t = eval(input())
for i in range(t):
	(n, k) = map(int, input().split())
	h = input()
	p = {}
	o = 0
	if n == k:
		print(1)
		continue
	for i in h:
		if i not in p:
			p[i] = 1
		else:
			p[i] += 1
	for i in p:
		o += p[i] // 2
	o1 = n - o * 2
	c = [0] * k
	c1 = 0
	for i in range(o):
		if c1 == k:
			c1 = 0
		c[c1] += 2
		c1 += 1
	c.sort()
	c2 = 0
	for i in range(len(c)):
		if o1 > 0:
			c[i] += 1
			o1 -= 1
		else:
			break
	r = min(c)
	if r % 2 == 0:
		if c.count(min(c)) <= c.count(min(c) + 2):
			print(r + 1)
		else:
			print(r)
	else:
		print(r)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	s = 0
	C = Counter(st)
	for i in C.values():
		s += i // 2
	ans = s // k * 2
	if n - ans * k >= k:
		ans += 1
	print(ans)


ttime = int(input())
for ccount in range(ttime):
	(n, k) = map(int, input().split())
	st = input()
	count = {}
	for c in st:
		count[c] = 0
	for c in st:
		count[c] += 1
	sm = 0
	for c in count:
		sm += count[c] - count[c] % 2
	start = sm // 2 // k * 2
	if len(st) - start * k >= k:
		start += 1
	print(start)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	A = d.values()
	A = list(A)
	(counter_1, counter_2) = (0, 0)
	for i in A:
		counter_2 += i // 2
		counter_1 += i % 2
	x0 = counter_1
	y0 = counter_2
	x0 += y0 % k * 2
	x0 = 1 if x0 >= k else 0
	ans0 = y0 // k * 2 + x0
	print(ans0)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	pal = input()
	color = defaultdict(int)
	for i in pal:
		color[i] += 1
	(single, pair) = (0, 0)
	for i in color:
		if color[i] % 2:
			single += 1
		pair += color[i] // 2
	single += pair % k * 2
	print(pair // k * 2 + 1) if single >= k else print(pair // k * 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ss = sorted(s)
	(cur, p, o) = (1, 0, 0)
	for i in range(1, len(ss)):
		if ss[i] == ss[i - 1]:
			cur += 1
		else:
			p += cur // 2
			o += cur % 2
			cur = 1
	p += cur // 2
	o += cur % 2
	print(int(p / k) * 2 + (o + p % k * 2 >= k))


t = int(input())
while t:
	(a, b) = map(int, input().split())
	s1 = input()
	d = {}
	for i in s1:
		d[i] = 1 + d.get(i, 0)
	c1 = 0
	c2 = 0
	for i in d.values():
		c1 += i // 2
		c2 += i % 2
	ans = 2 * (c1 // b)
	c2 += 2 * (c1 % b)
	if c2 >= b:
		ans += 1
	print(ans)
	t -= 1


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	cnt = [0] * 26
	for ele in s:
		cnt[ord(ele) - ord('a')] += 1
	(odd_cnt, even_cnt) = (0, 0)
	for i in range(26):
		if cnt[i] == 0:
			continue
		even_cnt += cnt[i] // 2
		odd_cnt += cnt[i] % 2
	res = even_cnt // k * 2
	odd_cnt += even_cnt % k * 2
	if odd_cnt >= k:
		res += 1
	print(res)


T = int(input())
for tc in range(T):
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	pair = 0
	count = 0
	for key in d.keys():
		if d[key] % 2 == 0:
			pair += d[key] // 2
		else:
			count += 1
			pair += d[key] // 2
	res = pair // k
	rem = pair % k
	if 2 * rem + count < k:
		print(2 * res)
	elif 2 * rem + count >= k:
		print(2 * res + 1)


import sys
from math import sqrt, gcd
from collections import deque, Counter
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007

def valid(le):
	val = 0
	if pair >= k:
		val += pair // k
		pair -= val
	if pair > 0 and odd > 0:
		val += 1
	return val >= le
for i in range(I()):
	(n, k) = M()
	s = S()
	d = {i: 0 for i in s}
	for i in s:
		d[i] += 1
	pair = 0
	odd = 0
	for i in d:
		pair += d[i] // 2
		if d[i] % 2:
			odd += 1
	(a, b) = (pair // k, pair % k)
	if 2 * b + odd < k:
		print(2 * a)
	else:
		print(2 * a + 1)


t = int(input())
DIC = {}
for _ in range(t):
	DIC.clear()
	(n, k) = map(int, input().split())
	s = input()
	for c in s:
		DIC[c] = DIC.get(c, 0) + 1
	tot = 0
	totPairs = 0
	for key in DIC:
		if DIC[key] % 2 != 0:
			tot += 1
			DIC[key] -= 1
		totPairs += DIC[key] // 2
	tot = min(tot, k)
	mn = totPairs // k * 2
	left = totPairs % k
	left *= 2
	if tot == 0:
		if left >= k:
			mn += 1
		print(mn)
	elif left == 0:
		if tot == k:
			print(mn + 1)
		else:
			print(mn)
	elif tot + left < k:
		print(mn)
	else:
		print(mn + 1)


from collections import *
TT = int(input())
for y in range(TT):
	(n, m) = map(int, input().split())
	s = input()
	d = defaultdict(int)
	for i in s:
		d[i] += 1
	c1 = c2 = 0
	for i in d:
		c2 += d[i] // 2
		if d[i] % 2 != 0:
			c1 += 1
	minn = c2 // m * 2
	c2 = c2 % m * 2 + c1
	if c2 >= m:
		print(minn + 1)
	else:
		print(minn)


from typing import Counter

def find(l, col, s: str):
	N = Counter(s)
	npair = 0
	for letter in N:
		npair += N[letter] // 2
	max_pair = npair // col
	remain = l - max_pair * 2 * col
	if remain >= col:
		return max_pair * 2 + 1
	else:
		return max_pair * 2
r = int(input())
for i in range(r):
	(l, col) = list(map(int, input().split()))
	s = input()
	print(find(l, col, s))


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = input()
	pairs = 0
	d = defaultdict(lambda : 0)
	for i in A:
		d[i] += 1
	for i in d.keys():
		pairs += d[i] // 2
	(l, r) = (0, n // k + 1)
	while l + 1 < r:
		x = (l + r) // 2
		if x % 2 == 0:
			if pairs >= k * x // 2:
				l = x
			else:
				r = x
		elif pairs >= x // 2 * k:
			l = x
		else:
			r = x
	print(l)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	freq = defaultdict(int)
	for ch in s:
		freq[ch] += 1
	pairs = 0
	singles = 0
	for i in freq:
		pairs += freq[i] // 2
		singles += freq[i] & 1
	if pairs < k:
		minLength = 1
	else:
		minLength = pairs // k * 2
		singles += pairs % k * 2
		if singles >= k:
			minLength += 1
	print(minLength)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = {}
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = 1
		else:
			d[s[i]] += 1
	pairs = 0
	ones = 0
	for e in d:
		pairs += d[e] // 2
		ones += d[e] % 2
	ans = 2 * (pairs // k)
	ones += 2 * (pairs % k)
	if pairs // k > 0 and ones >= n - pairs % k or ones >= k:
		ans += 1
	print(ans)


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = input()
		chrs = [0 for i in range(26)]
		for i in s:
			chrs[ord(i) - ord('a')] += 1
		(par, odd) = (0, 0)
		for i in chrs:
			par += i // 2
			odd += i % 2
		a = 2 * (par // k)
		odd += 2 * (par % k)
		if odd >= k:
			a += 1
		print(a)
main()


for j in range(int(input())):
	(n, k) = map(int, input().strip().split())
	s = input()
	ch = ''
	pa = 0
	for i in s:
		if i not in ch:
			ch += i
			a = s.count(i)
			pa += a // 2
	la = pa // k * 2
	if k == n:
		print(1)
	elif n - la * k < k:
		print(la)
	else:
		print(la + 1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	x = list(input())
	count = {}
	for ele in x:
		if count.get(ele, -1) == -1:
			count[ele] = 1
		else:
			count[ele] += 1
	pairs = 0
	single = 0
	for key in count.keys():
		if count[key] % 2 == 0:
			pairs += count[key] // 2
		else:
			pairs += count[key] // 2
			single += 1
	min_len = 2 * (pairs // k)
	single += (pairs - pairs // k * k) * 2
	if single >= k:
		min_len += 1
	print(min_len)


from collections import Counter

def main():
	T = int(input())
	for t in range(T):
		(l, k) = map(int, input().strip().split(' '))
		s = input()
		freq = Counter(s)
		rep = 0
		unique = 0
		for a in freq:
			rep += freq[a] // 2
			unique += freq[a] % 2
		pal = 2 * (rep // k)
		unique += 2 * rep - pal * k
		pal += min(unique // k, 1)
		print(pal)
main()


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	t = list(set(s))
	d = {i: 0 for i in s}
	for i in d:
		d[i] = s.count(i)
	pf = 0
	for i in d:
		pf += d[i] // 2
	mphl = pf // b
	mpl = 2 * mphl
	x = len(s) - mpl * b
	if x >= b:
		print(mpl + 1)
	else:
		print(mpl)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	c = Counter(input()).values()
	s = sum((i // 2 for i in c))
	print(s // k * 2 + (sum(c) - 2 * (s - s % k) >= k))


from collections import Counter

def solution():
	(n, k) = [int(i) for i in input().split()]
	c = Counter(input())
	pair = lone = 0
	for i in c.values():
		pair += i // 2
		lone += i % 2
	lone += pair % k * 2
	print(pair // k * 2 + (lone >= k))
t = int(input())
for _ in range(t):
	solution()


task_num = int(input().strip())
for task_id in range(task_num):
	len_and_color_num = list(map(int, input().strip().split()))
	color_num = len_and_color_num[1]
	letters = input().strip()
	letter_dict = {}
	for letter in letters:
		if letter in letter_dict.keys():
			letter_dict[letter] += 1
		else:
			letter_dict[letter] = 1
	pair_num = 0
	single_num = 0
	for letter in letter_dict.keys():
		if letter_dict[letter] % 2:
			single_num += 1
		pair_num += letter_dict[letter] // 2
	mini_pair = pair_num // color_num
	single_num += 2 * (pair_num % color_num)
	if single_num >= color_num:
		print(2 * mini_pair + 1)
	else:
		print(2 * mini_pair)


from collections import defaultdict
for _ in range(int(input())):
	charCount = defaultdict(int)
	(n, k) = map(int, input().split())
	s = input()
	for i in s:
		charCount[i] += 1
	count_2 = 0
	count_1 = 0
	for char in charCount:
		count_2 += charCount[char] // 2
		count_1 += charCount[char] % 2
	if count_1 + 2 * (count_2 % k) < k:
		print(2 * (count_2 // k))
	else:
		print(2 * (count_2 // k) + 1)


from collections import Counter

def solve(n, k, s):
	c = Counter(s)
	pairs = sum((c[x] // 2 for x in c))
	singles = sum((c[x] % 2 for x in c))
	(a, b) = divmod(pairs, k)
	result = 2 * a
	if 2 * b + singles >= k:
		result += 1
	return result
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	result = solve(n, k, s)
	print(result)


from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
import copy
from decimal import Decimal, getcontext
getcontext().prec = 32
MOD = 998244353
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	(n, k) = get.map()
	s = input()
	if n == k:
		print(1)
		return
	d = Counter(s)
	(singles, pairs) = (0, 0)
	for (a, b) in d.items():
		singles += b % 2
		pairs += b // 2
	ans = 0
	ans += 2 * (pairs // k)
	if n - ans * k >= k:
		print(ans + 1)
	else:
		print(ans)
for _ in range(int(input())):
	solve()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	A = d.values()
	A = list(A)
	flag = 1
	(counter_1, counter_2) = (0, 0)
	(counter_1_d, counter_2_d) = (0, 0)
	(counter_1_extra, counter_2_extra) = (0, 0)
	for i in A:
		if i % k == 0 and i // k % 2 and flag:
			flag = 0
			counter_2_extra = i - k
			counter_1_extra = k
			counter_2_d = i // 2
			counter_1_d = i % 2
		else:
			counter_2 += i // 2
			counter_1 += i % 2
	x0 = counter_1 + counter_1_d
	y0 = counter_2 + counter_2_d
	x0 += y0 % k * 2
	x0 = 1 if x0 >= k else 0
	x1 = counter_1 + counter_1_extra
	y1 = counter_2 + counter_2_extra // 2
	x1 += y1 % k * 2
	x1 = 1 if x1 >= k else 0
	ans0 = y0 // k * 2 + x0
	ans1 = y1 // k * 2 + x1
	print(max(ans0, ans1))


from collections import Counter
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	pairs = 0
	count = Counter(s)
	for element in count.values():
		(p, r) = divmod(element, 2)
		pairs += p
	answer = pairs // k * 2
	remain = n - answer * k
	if remain >= k:
		answer += 1
	print(answer)


from collections import defaultdict
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = defaultdict(int)
	for a in s:
		d[a] += 1
	l = []
	for a in d:
		l.append(d[a])
	p = 0
	n_p = 0
	for m in range(len(l)):
		p += l[m] // 2
		n_p += l[m] % 2
	sol = 2 * (p // k)
	rem = 2 * (p % k) + n_p
	if rem >= k:
		sol += 1
	print(sol)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = Counter(s)
	(odd, even) = (0, 0)
	for v in c.values():
		odd += v % 2
		even += v // 2
	ret = 2 * (even // k)
	if odd + 2 * (even % k) >= k:
		ret += 1
	print(ret)


def solve(n, k, s):
	dct = {}
	for i in range(n):
		dct[s[i]] = dct.get(s[i], 0) + 1
	pairs = 0
	single = 0
	for ele in dct:
		if dct[ele] > 1:
			pairs += dct[ele] // 2
		single += dct[ele] % 2
		dct[ele] = 0
	ans = 0
	remain = 0
	if pairs >= k:
		ans = 2 * (pairs // k)
		single += 2 * (pairs % k)
	else:
		single += 2 * (pairs % k)
	if single >= k:
		print(ans + 1)
	else:
		print(ans)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	solve(n, k, s)


class CodeForces1624D:

	def solve(self, k: int, s: str) -> int:
		hash_map = [0 for _ in range(0, 27)]
		for c in s:
			hash_map[ord(c) - ord('a')] += 1
		(pairs_sum, odd_sum) = (0, 0)
		for count in hash_map:
			pairs_sum += count // 2
			odd_sum += count % 2
		ans = 2 * (pairs_sum // k)
		odd_sum += 2 * (pairs_sum % k)
		return ans + (1 if odd_sum >= k else 0)

def main():
	t = int(input())
	for _ in range(t):
		inp = list(map(int, input().split()))
		(n, k) = (inp[0], inp[1])
		s = str(input())
		print(CodeForces1624D().solve(k, s))
main()


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	counts = Counter(s)
	singles = 0
	pairs = 0
	for c in counts:
		pairs += counts[c] // 2
		singles += counts[c] % 2
	ans = 2 * (pairs // k)
	ans += singles + 2 * (pairs % k) >= k
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = list(input())
	counter = Counter(S)
	C = list(counter.values())
	(cntPairs, cntOdd) = (0, 0)
	for cnt in C:
		cntPairs += cnt // 2
		cntOdd += cnt % 2
	ans = 2 * (cntPairs // k)
	cntOdd += 2 * (cntPairs % k)
	if cntOdd >= k:
		ans += 1
	print(ans)


import sys, string

def palindromes_coloring(n, k, s):
	counts = {ch: 0 for ch in string.ascii_lowercase}
	for ch in s:
		counts[ch] += 1
	even_count = 0
	for (ch, count) in counts.items():
		even_count += 2 * (count // 2)
	odd_count = n - even_count
	l = even_count // (k * 2) * 2
	even_count -= l * k
	if even_count + odd_count >= k:
		l += 1
	return l
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	sys.stdout.write(f'{palindromes_coloring(n, k, s)}\n')


import sys
import re
import math
from math import log2 as lg
from decimal import *
from collections import deque
import random
import heapq
import itertools
const = 1000000007
ep = 1e-10

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	line = get()
	(m, k) = (line[0], line[1])
	d = {}
	s = input()
	for term in s:
		if term in d:
			d[term] += 1
		else:
			d[term] = 1
	(even, odd) = (0, 0)
	for t in d:
		term = d[t]
		if term % 2 == 1:
			odd += 1
		even += term // 2
	ans = even // k * 2
	odd += even % k * 2
	if odd >= k:
		ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	odds = 0
	eves = 0
	for i in d:
		if d[i] % 2 == 0:
			num = d[i] // 2 * 2
			eves += num
		else:
			odds += 1
			num = d[i] // 2 * 2
			eves += num
	pairs = eves // 2
	minlength = pairs // k * 2
	if pairs % k == 0:
		if odds >= k:
			minlength += 1
			print(minlength)
		else:
			print(minlength)
	else:
		left = pairs % k * 2
		if left + odds >= k:
			minlength += 1
		print(minlength)


def problem4(n, k, string):
	counter = [0] * 26
	for c in string:
		counter[ord(c) - ord('a')] += 1
	pairs = ans = remainder = 0
	for num in counter:
		pairs += num // 2
		remainder += num % 2
	ans = pairs // k * 2
	if pairs % k * 2 + remainder >= k:
		ans += 1
	print(max(ans, 1))
for _ in range(int(input())):
	(n, k) = [int(num) for num in input().split(' ')]
	string = input()
	problem4(n, k, string)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	li = input()
	alpha = [0 for __ in range(26)]
	cnt1 = 0
	cnt2 = 0
	for w in li:
		alpha[ord(w) - 97] += 1
		if alpha[ord(w) - 97] > 1:
			alpha[ord(w) - 97] -= 2
			cnt2 += 1
	cnt1 = sum(alpha)
	res = 0
	res += cnt2 // k * 2
	cnt2 %= k
	cnt1 += cnt2 * 2
	if cnt1 >= k:
		res += 1
	print(res)


from collections import Counter

def solve():
	(n, k) = map(int, input().split())
	s = input()
	counter = Counter(s)
	pairs = sum((x // 2 for x in counter.values()))
	ones = sum((1 for x in counter.values() if x % 2 == 1))
	return pairs // k * 2 + (1 if pairs % k * 2 + ones >= k else 0)
t = int(input())
for c in range(t):
	print(solve())


def solve(s, k):
	ans = 0
	c = dict()
	for a in s:
		if a not in c:
			c.__setitem__(a, 0)
		c[a] += 1
	sort_c = sorted(c.items(), key=lambda x: x[1], reverse=True)
	count = 0
	total = 0
	middle = 0
	for item in sort_c:
		count += 1
		total += item[1]
		if item[1] % 2 == 1:
			total += -1
			middle += 1
	ans = int(total / k)
	if middle + total % k >= k and ans % 2 == 0:
		ans += 1
	return max(ans, 1)
test = int(input())
for t in range(0, test):
	(n, k) = list(map(int, input().split()))
	s = input()
	print(solve(s, k))


for u in range(int(input())):
	(n, k) = map(int, input().split())
	x = input()
	y = [0] * 26
	for i in range(n):
		y[ord(x[i]) - ord('a')] += 1
	t = 0
	for i in range(26):
		t += y[i] // 2
	l = 1
	r = n // k + 1
	while l <= r:
		mid = (l + r) // 2
		if mid % 2 == 0 and t >= k * (mid // 2) or (mid % 2 and t >= k * (mid // 2) and (n >= 2 * k * (mid // 2) + k)):
			l = mid + 1
			ans = mid
			continue
		r = mid - 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	arr = [0 for i in range(26)]
	for i in range(n):
		arr[ord(s[i]) - ord('a')] += 1
	pairs = 0
	for i in range(26):
		pairs += arr[i] // 2
	rem = n - 2 * pairs
	ans = pairs // k
	pairs = pairs - ans * k
	ans = ans * 2
	rem = rem + pairs * 2
	if rem >= k:
		ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	stats = {}
	for c in s:
		if c not in stats.keys():
			stats[c] = 1
		else:
			stats[c] = stats[c] + 1
	tot_pair_cnt = 0
	extras_1 = 0
	total = 0
	for (ky, v) in stats.items():
		total += v
		tot_pair_cnt += v // 2
		extras_1 += v % 2
	extras = extras_1 + tot_pair_cnt % k * 2
	res = 0
	if extras >= k:
		res += 1
	res += tot_pair_cnt // k * 2
	print(res)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	counts = Counter(s)
	ps = [0] * 2
	for key in counts.keys():
		ps[1] += counts[key] % 2
		ps[0] += counts[key] // 2
	ps[1] += 2 * (ps[0] % k)
	ans = 2 * (ps[0] // k) + (1 if ps[1] >= k else 0)
	print(ans)


size = int(input())
for i in range(size):
	str1 = list(map(int, input().split()))
	n = str1[0]
	k = str1[1]
	str1 = input()
	table_c = []
	table_n = []
	for i in range(n):
		if str1[i] in table_c:
			ndx = table_c.index(str1[i])
			table_n[ndx] += 1
		else:
			table_c.append(str1[i])
			table_n.append(1)
	table = sorted(table_n)
	s = len(table)
	even = [int(table[t] / 2) for t in range(s)]
	odd = [table[t] % 2 for t in range(s)]
	seven = sum(even)
	sodd = sum(odd)
	tt = seven % k
	ncount = 0
	if n == k:
		print('1')
		continue
	if tt == 0:
		count = int(seven / k)
	else:
		count = int(seven / k)
		sodd = tt * 2 + sodd
	if sodd >= k:
		ncount = 1
	print(count * 2 + ncount)


t = int(input())

def solve():
	(n, k) = list(map(int, input().split()))
	s = input()
	letters = [0] * 26
	for i in s:
		x = ord(i) - ord('a')
		letters[x] += 1
	count_double = 0
	count_once = 0
	for i in range(len(letters)):
		y = letters[i] // 2
		count_double += y
		letters[i] %= 2
		if letters[i] == 1:
			letters[i] = 0
			count_once += 1
	x = count_double // k
	count_double %= k
	answer = x * 2
	if count_double * 2 + count_once >= k:
		answer += 1
	print(answer)
for i in range(t):
	solve()


from collections import Counter
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = Counter(s)
	ev = 0
	od = 0
	for i in c:
		ev += c[i] // 2
		od += c[i] % 2
	s = ev // k * 2
	od += ev % k * 2
	if od >= k:
		print(s + 1)
	else:
		print(s)