给定一个长度为 $$$n$$$ 的字符串 $$$s$$$ 和一个数字 $$$k$$$。让我们用 $$$rev(s)$$$ 表示反转的字符串 $$$s$$$ (即 $$$rev(s) = s_n s_{n-1} ... s_1$$$)。您可以对字符串应用两种操作之一:
- 将字符串 $$$s$$$ 替换为 $$$s + rev(s)$$$
- 将字符串 $$$s$$$ 替换为 $$$rev(s) + s$$$
对原始字符串 $$$s$$$ 执行精确的 $$$k$$$ 操作(可能是不同类型的),可以得到多少个不同的字符串?
在此语句中,我们将字符串 $$$s$$$ 和 $$$t$$$ 的串联表示为 $$$s + t$$$。换句话说,$$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$,其中 $$$n$$$ 和 $$$m$$$ 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。接下来的 $$$2 \cdot t$$$ 行包含 $$$t$$$ 测试用例:
测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$)——分别是字符串的长度和操作的数量。
测试用例的第二个字符串包含一个由小写拉丁字母组成的长度为 $$$n$$$ 的字符串 $$$s$$$。
输出
对于每个测试用例,在单独的行上打印答案(即,经过 $$$k$$$ 操作后可以获得的不同字符串的数量)。
可以证明,在给定的约束下,答案不会超过$$$10^9$$$。
示例
输入 #1
4 3 2 aab 3 3 aab 7 1 abacaba 2 0 ab
输出 #1
2 2 1 1
注意
在示例的第一个测试用例中:
第一次操作后,字符串 $$$s$$$ 可以变成 aabbaa 或 baaaab。第二次操作后,$$$s$$$ 有 2 种可能:aabbaaaabbaa 和 baaaabbaaaab。