#2028. 「NOI 2023」字符串

小 Y 是一名大学生，最近正在研究字符串方向的问题。

小 Y 了解到关于字符串的如下定义:

• 给定一个长度为 的字符串 ，我们定义其子串 （）为选择 , 将其顺次拼接得到的新字符串。
• 给定一个长度为 的字符串 ，我们定义其翻转后的结果 为将 顺次拼接，也就是将字符串反序拼接得到的字符串。
• 给定两个长度均为 的字符串 ，我们定义 的字典序小于 当且仅当存在 ，使得对于任意 ，，且 。

在了解了上述定义后，小 Y 想到了这样的问题:

给定一个长度为 的字符串 。有 次询问，每次询问给定两个参数 。你需要求出有多少 ，满足如下条件:

• 。
• 字典序小于 。

小 Y 想求助你帮忙解决这一问题。

从文件 string.in 中读取数据。

本题有多组测试数据。

输入的第一行包含两个整数 ，分别表示测试点编号和测试数据组数。 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含两个正整数 ，表示子符串长度和询问次数。

输入的第二行包含一个长度为 的仅包含小写字母的字符串 。

输入的接下来 行，每行包含两个正整数 。表示一次询问，保证 。

输出到文件 string.out 中。

对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 的个数。

样例 1 输入

0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3

样例 1 输出

4
0
3
2
0
2

样例 1 解释

对于第一组数据的第一组询问：

• 时，，。
• 时，，。
• 时，，。
• 时，，。

这四种情况中， 的字典序均小于 。因此答案为 。

样例 2

见附件中的 string/string2.in 与 string/string2.ans。

该样例数据范围满足测试点 。

样例 3

见附件中的 string/string3.in 与 string/string3.ans。

样例 4

见附件中的 string/string4.in 与 string/string4.ans。

该样例数据范围满足测试点 。

对于所有测试数据保证：，，，，字符串 仅包含小写字母。

特殊性质 A：保证字符串中仅包含字符 和 ，且每个字符独立等概率地在 和 中选择。

特殊性质 B：保证字符串中的相邻字符互不相同。