题目描述

真正的愚蠢每次都能击败人工智能。

——Terry Pratchett，《Hogfather》，《碟形世界》

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$。我们用 $rev(s)$ 表示字符串 $s$ 的反转（即 $rev(s) = s_n s_{n-1} \ldots s_1$）。你可以对字符串进行以下两种操作之一：

• 用 $s + rev(s)$ 替换字符串 $s$；
• 用 $rev(s) + s$ 替换字符串 $s$。

在原始字符串 $s$ 上恰好执行 $k$ 次操作（每次操作可以任选其中一种），最终能得到多少个不同的字符串？

在本题中，我们用 $s + t$ 表示字符串 $s$ 和 $t$ 的连接。换句话说，$s + t = s_1 s_2 \ldots s_n t_1 t_2 \ldots 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$。

说明/提示

在示例的第一个测试用例中：

第一次操作后，字符串 $s$ 可以变为 aabbaa 或 baaaab。第二次操作后，$s$ 有两种可能：aabbaaaabbaa 和 baaaabbaaaab。

由 ChatGPT 4.1 翻译

样例

4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

2
2
1
1