您有一个由小写拉丁字母组成的字符串 $$$s$$$。
您可以为一些字母涂上从 $$$1$$$ 到 $$$k$$$ 的颜色。没有必要画出所有的字母。但对于每种颜色,必须有一个用该颜色绘制的字母。
然后您可以根据需要多次交换任意两个相同颜色的符号。
之后,将创建 $$$k$$$ 字符串,其中 $$$i$$$ 将包含以 $$$i$$$ 颜色着色的所有字符,按其在字符串 $$$s$$$ 中的顺序写入。
你的任务是给字符串的字符着色,使得所有生成的 $$$k$$$ 字符串都是回文,并且这些 $$$k$$$ 字符串中最短的字符串的长度尽可能大。
如果您需要澄清,请阅读示例的第一个测试用例的注释。
回想一下,如果一个字符串从左到右和从右到左读取的方式相同,那么它就是回文。例如,字符串 abacaba、cccc、z 和 dxd 是回文,但字符串 abab 和 aaabaa 则不是。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中输入数据集的数量。
输入数据集的描述如下。
每个输入数据集描述的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 字符串的长度及其字母可以绘制的颜色数。每个输入数据集的描述的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由拉丁字母的小写字母组成。
保证所有测试用例的 n 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每组输入数据,输出一个整数——可以获得的最短回文串的最大长度。
示例
输入 #1
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
输出 #1
3 2 1 1 1 5 1 1 3 3
注意
- 在第一个测试用例中,$$$s$$$="bxyaxzay",$$$k=2$$$。我们在字符串中使用从 $$$1$$$ 到 $$$8$$$ 的索引。以下着色将起作用:$$$\mathtt{\mathbf{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$$$(字母 z 保持未着色)。绘制后:交换两个红色字符(索引为$$$1$$$和$$$4$$$),我们得到$$$\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$$$; 交换两个蓝色字符(索引为 $$$5$$$ 和 $$$8$$$),我们得到 $$$\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{a}\color{blue}{x}}}$$$。现在,对于两种颜色中的每一种,我们从左到右写出相应的字符,我们得到两个字符串 $$$\mathtt{\mathbf{\color{red}{aba}}}$$$ 和 $$$\mathtt{\mathbf{\color{blue}{xyyx}}}$$$。两者都是回文,最短的长度是$$$3$$$。可以证明,最短回文的最大长度是无法实现的。
- 在第二组输入数据中,以下着色是合适的:$$$[1, 1, 2, 2, 3, 3]$$$。无需交换角色。接收到的两个字符串都等于 aa,它们是回文,长度为 $$$2$$$。
- 在第三组输入数据中,您可以为任何字符着色并将其放入字符串中。
- 在第四组输入数据中,您可以将第 $$$i$$$ 个字符着色为 $$$i$$$ 颜色。
- 在第五组输入数据中,可以用一个字符的每种颜色来着色。
- 在第六组输入数据中,以下着色是合适的:$$$[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]$$$。重新排列字符,得到回文 abcba 和 acbca。