对于长度为 的字符串 ，我们将字符串 定义为以下内容的连接： ● 的全部奇数位，按字典序从小到大排序； ● 的全部偶数位，按字典序从大到小排序。 现在，对于长度为 的字符串 ，你需要取出它的全部长度为 的子串，按照上方所述的步骤进行构造，能构造出多少个不相同的新字符串？ 在本题中，字符的字典序即 码，即 。 如果字符串 可以通过从字符串 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则字符串 是字符串 的子串。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行上输入两个整数 代表字符串长度、和询问长度。第二行输入一个长度为 ，且由大小写字母混合构成的字符串 ，代表初始串。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表构造出的新字符串数量。