CF1624D.Palindromes Coloring

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.

你有一个由小写拉丁字母组成的字符串 $s$。

你可以将其中一些字符染成从 $1$ 到 $k$ 的若干种颜色。不必将所有字符都染色，但每种颜色至少需染一个字符。

之后，你可以对任意两个同色字符进行任意次数的交换（即：同色字符的位置可任意重排）。

接着，将生成 $k$ 个字符串：第 $i$ 个字符串包含所有被染成颜色 $i$ 的字符，并按它们在原字符串 $s$ 中的原始顺序排列。

你的任务是为字符串 $s$ 的字符染色，使得所生成的 $k$ 个字符串均为回文串，并且这 $k$ 个字符串中最短者的长度尽可能大。

若需进一步理解，请参阅示例中第一个测试用例的注释说明。

回顾：若一个字符串从左到右读与从右到左读完全相同，则称其为回文串。例如，字符串 abacaba、cccc、z 和 dxd 是回文串，而 abab 和 aaabaa 则不是。

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$.

输入数据的第一行包含一个整数 $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$。

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

对于每组输入数据，输出一个整数——所能得到的最短回文串的最大长度。

• 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{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{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{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$;
  • swap two blue characters (with the indices $5$ and $8$), we get $\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{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{\color{red}{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.

• 在第一个测试用例中，$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。