题目描述

给定一个长度为 $n$ 的小写字母字符串。你需要使用字符串中的字符组成恰好 $k$ 个回文串，每个字符最多使用一次。

一个字符串从左向右读和从右向左读完全相同，则称它为回文串。

请合理分配字符，使这 $k$ 个回文串中最短的一个尽可能长，并输出这个最大长度。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

每组数据的第一行包含两个整数 $n$ 和 $k$。

每组数据的第二行包含一个长度为 $n$ 的小写字母字符串 $s$。

输出格式

对于每组数据，输出一行一个整数，表示最短回文串长度的最大值。

3
7 2
aaabbcc
5 3
aaaaa
6 2
abcdef

3
1
1

数据范围与提示

• $1 \le T \le 100$
• $1 \le k \le n$
• $1 \le n \le 2\times10^5$
• 所有测试数据中 $n$ 的总和不超过 $2\times10^5$
• 字符串仅包含小写英文字母