现在有一款风靡全球的新游戏：Palworld。在游戏中，你的目标是创造最长的回文串。（这是一个益智游戏！）

游戏开始时，有一个由 $n$ 个小写英文字母组成的字符串 $S$。同时给定一个整数 $k$。作为玩家，你必须执行且仅执行一次以下操作：

• 选择一个下标 $i$ ($0 \le i \le n$)，并在 $S$ 的下标 $i$ 之后插入最多 $k$ 个字符。选择 $i = 0$ 意味着在 $S$ 的最前面插入最多 $k$ 个字符。

你在游戏中的得分等于操作后字符串中最长回文子串的长度。

请问你能得到的最高得分是多少？

说明：

• 回文串是指一个正读和反读都一样的字符串。
• 子串是指通过删除字符串前面和/或后面的若干个字符（可能为零）而得到的字符串。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例包含两行：

• 第一行包含 $n$ 和 $k$，分别表示 $S$ 的长度和允许插入的字符数量。
• 第二行包含字符串 $S$。

数据范围：

• $1 \le t \le 10^4$
• $1 \le n \le 2 \cdot 10^5$
• $1 \le k \le 100$
• $S$ 仅包含字符 $a$ 到 $z$。
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$

输出格式

对于每个测试用例，输出一行，包含一个整数：操作后字符串中最长回文子串的最大可能长度。

样例

输入 1

4
1 3
a
4 1
icpc
4 2
icpc
8 4
icecream

输出 1

4
5
5
11

说明

• 在第一个样例中，你可以插入 3 个字符将 $S$ 变为 "abba"，这是一个长度为 4 的回文串。
• 在第二个样例中，最优方案是在 $S$ 后追加 "i"，形成 "icpci"，这是一个长度为 5 的回文串。
• 在第三个样例中，即使允许插入 2 个字符，我们也无法获得更长的回文串。
• 在第四个样例中，一个最优的最终字符串是 "imaercecream"，其中子串 "maercecream" 是一个长度为 11 的回文串。