题目内容

给定一个由大小写英文字母组成的序列，以及一个整数窗口长度 $x$。对于序列中每一个长度为 $x$ 的连续片段，我们按照以下规则生成一个新序列：

• 计算 $p = \lfloor x / 2 \rfloor$，将片段划分为前 $p$ 个字符和后 $x-p$ 个字符。
• 将片段的前 $p$ 个字符按字符从小到大的顺序（升序）排列，得到第一部分。
• 将整个片段的所有字符按字符从大到小的顺序（降序）排列，得到第二部分。
• 将后 $x-p$ 个字符按字符从小到大的顺序排列，得到第三部分。
• 将第一部分、第二部分、第三部分依次拼接，构成变换后的序列。

现给出一个长度为 $n$ 的初始序列，试求所有长度为 $x$ 的连续片段经上述变换后，能够得到多少个不同的新序列。

约束：测试数据组数不超过 $100$，序列长度 $n$ 不超过 $100$，$1 \le x \le n$。序列仅由大小写英文字母组成。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来每组数据包含两行： 第一行包含两个整数 $n$ 和 $x$，分别表示序列长度和窗口长度。 第二行包含一个长度为 $n$ 的由大小写字母组成的序列。

输出描述

对于每组测试数据，输出一行一个整数，表示变换后得到的不同序列的数量。

样例1

输入

2
3 1
aAb
4 4
Badc

输出

3
1

说明

包含两组测试数据。

第一组：$n=3, x=1$。此时 $k = \lfloor 1/2 \rfloor = 0$，前 $0$ 个字符为空，后 $1$ 个字符即为窗口自身。对于每个窗口字符 $c$，第一部分为空，第二部分为 $c$ 降序排列仍为 $c$，第三部分为 $c$ 升序排列仍为 $c$，因此变换后的字符串为 $c$ 与 $c$ 拼接，即 cc。三个窗口字符分别为 a、A、b，变换得到 aa、AA、bb，共有 3 种不同序列，输出 3。

第二组：$n=4, x=4$。$k = \lfloor 4/2 \rfloor = 2$。唯一的窗口是整个序列 Badc。前 $2$ 个字符 Ba 升序排序：由于 B 的 ASCII 码 66 小于 a 的 97，结果为 Ba。整个序列降序排序：字符 ASCII 码从大到小为 d(100) > c(99) > a(97) > B(66)，结果为 dcaB。后 $2$ 个字符 dc 升序排序结果为 cd。依次拼接得到 BadcaBcd。只有一个窗口，因此不同序列数量为 1，输出 1。

样例2

输入

1
5 3
ababa

输出

2

说明

$n=5, x=3$，$k = \lfloor 3/2 \rfloor = 1$。共有三个长度为 $3$ 的窗口：aba（位置 $0$ 到 $2$）、bab（位置 $1$ 到 $3$）和 aba（位置 $2$ 到 $4$）。

对于窗口 aba：前 $1$ 个字符升序为 a；整个窗口降序排列为 b、a、a（ASCII 码 b(98) > a(97)），得到 baa；后 $2$ 个字符 ba 升序为 ab。拼接得 abaaab。

对于窗口 bab：前 $1$ 个字符升序为 b；整个窗口降序排列为 b、b、a，得到 bba；后 $2$ 个字符 ab 升序为 ab。拼接得 bbbaab。

窗口 aba 出现了两次，变换后字符串相同，因此不同序列只有 abaaab 和 bbbaab 两种，输出 2。

样例3

输入

1
4 2
aaaa

输出

1

说明

$n=4, x=2$，序列全为相同字符 a。所有窗口均为 aa，完全相同。$k = \lfloor 2/2 \rfloor = 1$。对于窗口 aa：前 $1$ 个字符升序为 a；整个窗口降序排列为 aa；后 $1$ 个字符升序为 a。拼接结果为 aaaa。全部窗口变换后均得到 aaaa，故不同序列数量为 1。