CF1634A.Reverse and Concatenate

Real stupidity beats artificial intelligence every time.

— Terry Pratchett, Hogfather, Discworld

You are given a string $s$ of length $n$ and a number $k$. Let's denote by $rev(s)$ the reversed string $s$ (i.e. $rev(s) = s_n s_{n-1} ... s_1$). You can apply one of the two kinds of operations to the string:

• replace the string $s$ with $s + rev(s)$
• replace the string $s$ with $rev(s) + s$

How many different strings can you get as a result of performing exactly $k$ operations (possibly of different kinds) on the original string $s$?

In this statement we denoted the concatenation of strings $s$ and $t$ as $s + t$. In other words, $s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$, where $n$ and $m$ are the lengths of strings $s$ and $t$ respectively.

真正的愚蠢永远胜过人工智能。

——特里·普拉切特，《 Hogfather 》，《碟形世界》

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

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

对原始字符串 $s$ 恰好执行 $k$ 次操作（每次操作可以是上述两种类型之一），最多能得到多少个不同的字符串？

在本题中，我们用 $s + t$ 表示字符串 $s$ 与 $t$ 的拼接。换言之，若 $s$ 和 $t$ 的长度分别为 $n$ 和 $m$，则 $s + t = s_1 s_2 \dots s_n t_1 t_2 \dots t_m$。

The first line contains one integer $t$ ($1 \le t \le 100$) — number of test cases. Next $2 \cdot t$ lines contain $t$ test cases:

The first line of a test case contains two integers $n$ and $k$ ($1 \le n \le 100$, $0 \le k \le 1000$) — the length of the string and the number of operations respectively.

The second string of a test case contains one string $s$ of length $n$ consisting of lowercase Latin letters.

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的 $2 \cdot t$ 行包含 $t$ 个测试用例：

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100$，$0 \le k \le 1000$），分别表示字符串的长度和操作次数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

For each test case, print the answer (that is, the number of different strings that you can get after exactly $k$ operations) on a separate line.

It can be shown that the answer does not exceed $10^9$ under the given constraints.

对于每个测试用例，在单独一行中输出答案（即：恰好执行 $k$ 次操作后所能得到的不同字符串的个数）。

在给定约束条件下，可以证明该答案不超过 $10^9$。

In the first test case of the example:

After the first operation the string $s$ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $s$: aabbaaaabbaa and baaaabbaaaab.

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

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