题目描述

所谓指数爆炸，其实并不是真正的爆炸。指数爆炸是指数字呈现爆炸式增长。如果遇到的问题包含指数爆炸，一旦处理不好，该问题可能会膨胀到难以收拾的地步。

相反，若能寻得指数爆炸背后的本质，[指数爆炸]便不攻自破了。

你现在得到了一个长度为 $n$ 的字符串 $s$，这个字符串均 小写拉丁字母 ( a ~ z ) 组成。你需要对这个字符串进行 次操作，每次操作你可以在下述两种变换方式中选择一种:

• 将 $s$ 替换为 $s+rev(s)$;
• 将 $s$ 替换为 $rev(s)+s$;

其中 $rev(s)$ 是指将 $s$ 反转后的字符。 + 运算是指将两个字符 拼接。例如，对 acad 进行第一种操作后，$s$ 变为 acad + daca = acaddaca

不难发现，最终的字符串长度为 $n \times 2^k$

你现在的任务是，在 $k$ 次操作后，有多少种可能的 不同 的字符串。两个字符串 $s$，$t$ 不同当且仅当存在一个位置 $i$ 使得 $s_i \ne t_i$。

输入格式

第一行包含一个整数 工，代表多组测试组数，即你需要解决 $T$ 个任务。

接下来一共 $2T$ 行，每两行依次描述一个任务:

第一行包含两个整数 $n$,$k$，代表字符串 $s$ 的长度以及操作数；

第二行包含一个长度为 $n$ 的仅由小写拉丁字母组成的字符串 $s$ 。

数据范围

对于 40% 的数据，$1 \le T \le 10$，$1 \le n \le 10$，$0 \le k \le 10$;

对于 100% 的数据，$1 \lt T,n \le 1000$，$0 \le k \le 1000$

输出格式

共 $T$ 行，第 $i$ 行输出第 $i$ 个任务的答案。

样例

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

2
2
1
1