A14778. 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.

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.

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.

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.