小 A 拥有一个仅由小写字母组成的字符串S。

可以将其中的字母染色为 k 种颜色。并不是每个字母都需要进行染色，但是要求对于每种颜色，必须至少有一个字母由该颜色染色。

然后可以交换相同颜色的字母任意次。

操作结束后意味着小 A 将拥有 k 种颜色的子串，第 i 个子串包含了所有染色为第 i 种颜色的字母。

小 A 的任务是对这个字符串 S 进行染色，但是要保证这 k 个子串可以成为回文子串，并且其中最短的子串长度尽可能长。

如果字符串从左到右和从右到左的读取结果相同那么它就是回文的。比如字符串a，aba，aaaa是回文的，但是abab，aaabaa不是回文的。

第一行读入一个整数 t，表示有 t 组测试数据。

接下来会读入 t 组测试数据：

每组测试数据的第一行为两个整数 n 和 k,分别表示字符串 S 的长度 和 可以染色的颜色种类 。

第二行为一个仅包含小写字母的字符串 S。

输出 t 个整数，每行一个，表示对于每组数据的字符串 S 染色后所能形成的 k 个子串中最短的回文串最长的长度。

样例 1 解释

可以把长度为 8 的字符串 bxyaxzay 染色为两种颜色。

染色后可以变为：\red{b}\blue{xy}\red{a}\blue{xz}\red{a}\blue{y} 。

我们可以得到两个颜色的子串分别为：\red{baa}，\blue{xyxzy} 。

这两个子串都已通过交换位置变为回文子串：\red{aba}， \blue{xyzyx} 。

最短长度为 3，且无法再找到让其变得更大的方案。

数据规模

1 \leq t \leq 10000 。

1 \leq k \leq n \leq 2 \times 10^5 。

数据保证每组测试用例中 n 的和不会超过 2 \times 10^5 。

月赛字符串贪心二分