解题思路

设

对于某个长度为 $x$ 的子串 $t$，构造出的新字符串由三部分拼接而成：

题目内容

对于长度为 $m$ 的字符串 $t_1t_2...t_m$ 和整数 $i(≤i≤m)$，我们将字符串 $f_i(t)$ 定义为以下内容的连接：

• $t$ 的前 $\lfloor \frac{i}{2} \rfloor$ 个字符，按字典序从小到大排序；

• $t$ 整串，按字典序从大到小排序;

• $t$ 除去前 $\lfloor \frac{i}{2} \rfloor$ 个字符外的剩余字符，按字典序从小到大排序。

现在，对于长度为 $n$ 的字符串 $s_1s_2...s_n$，你需要取出它的的全部长度为 $x$ 的子串，且令 $i=x$ ，按照上方所述的步骤进行构造，能构造出多少个不相同的新字符串？

定义子串为，从原字符串中，连续的选择一段字符(可以全选、可以不选)组成的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤100)$ 代表数据组数，每组测试数据描述如下：

第一行上输入两个整数 $n,x(1≤n≤100;1≤x≤n)$ 代表字符串长度、和询问长度。

第二行输入一个长度为 $n$ ，且由大小写字母混合构成的字符串 $s$，代表初始串。

输出描述

在一行上输出一个整数，代表构造出的新字符串数量。

样例1

输入

2
5 4
bAbbb
7 3
nuhhhhh

输出

1
3

说明

对于第一组测试数据，长度为 $4$ 的不同子串有 $bAbb$ 和 $Abbb$ :

• 对于 $bAbb$，构造得到 $f4 (bAbb)= Ab +bbbA +bb$：

  • 前 $\frac{i}{2}$ 个字符，按字典序从小到大排序为 $Ab$
  • 整串，按字典序从大到小排序为 $bbbA$;
  • 除去前 $\frac{i}{2}$ 个字符外的剩余字符，按字典序从小到大排序为 $bb$ 。

• 对于 $Abbb$，构造得到 $f4 (Abbb)= Ab +bbbA +bb$ 。