说明

时间限制：1 Sec 内存限制：256 MB 输入文件：string.in 输出文件：string.out

小明得到一个全部由小写字母组成的字符串 $s$，长度为 $n$。

然后，佳佳给了他一个整数 $k$（$k \le n$），要求他为字符串 $s$ 染色，染 $k$ 种颜色。

每种颜色至少要染一个字符，每个字符只能被染一种颜色，可以有一些字符不染色。

染完色之后，小明可以把 $s$ 中相同颜色的字符随意调换位置。

然后，佳佳来验收啦。她会把每种颜色对应的字符都挑出来，按它们在 $s$ 中原有的前后位置排在一起，形成 $k$ 个字符串。如果每个字符串都是回文串，那么验收就通过了。

最后，小明会得到奖励。在所有这些 $k$ 个字符串中，长度最短的字符串，它的长度就是奖励。小明希望得到尽量多的奖励，请你帮他计算一下，他最多能得到多少奖励。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 行，第 $i$ 行为第 $i$ 组询问，包括两行：

第一行为一个整数 $k$，第二行为一个全部由小写字母组成的字符串 $s$，长度为 $n$。

输出格式

$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数，表示小明最多可以得到的奖励是多少。

样例

样例 1

10
2
bxyaxzay
3
aaaaaa
1
abcdef
6
abcdef
2
dxd
2
abcabcabcac
6
sipkic
2
eatoohd
1
llw
2
bfvfbv

3
2
1
1
1
5
1
1
3
3

样例说明：

在第 $1$ 组询问中，s="bxyaxzay"，k=2。我们用 $1$ 到 $8$ 的编号表示字符串中的位置。以下染色方案可行：bxyaxzay（字母 z 未被染色）。染色后：

• 交换两个红色字符（编号 $1$ 和 $4$），得到 axybxzay；
• 交换两个蓝色字符（编号 $5$ 和 $8$），得到 axybyzax。

现在，对于每种颜色，从左到右写出对应的字符，得到两个字符串 aba 和 xyyx。它们都是回文串，最短的长度为 $3$。可以证明，最短回文串的最大长度无法超过 $3$。

在第 $2$ 组询问中，以下染色方案可行：aaaaaa。无需交换字符。得到的字符串均为 aa，都是回文串，长度为2。

在第 $3$ 组询问中，可以任意染色一个字符并取出来作为字符串。

在第 $4$ 组询问中，可以将第 $i$ 个字符染成第 $i$ 种颜色。

在第 $5$ 组询问中，可以每种颜色各染一个字符。

在第 $6$ 组询问中，以下染色方案可行：abcabcabcac。重新排列字符，可以得到回文串 abcba 和 acbca。

数据范围

$1 \le t \le 10^4$

$1 \le k \le n \le 2 \times 10^5$

题目保证所有询问中的 $n$ 之和不超过 $2 \times 10^5$