下发文件：http://119.27.163.117/download.php?type=problem&id=274
题目描述
小 Y 是一名大学生，最近正在研究字符串方向的问题。
小 Y 了解到关于字符串的如下定义:
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。
- 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a[j] = b[j]$，且 $a[i] < b[i]$。
在了解了上述定义后，小 Y 想到了这样的问题:
给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件: - $1 \leq l \leq r$。 - $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。
小 Y 想求助你帮忙解决这一问题。
输入格式
本题有多组测试数据。
输入的第一行包含两个整数 $c, t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含两个正整数 $n, q$，表示子符串长度和询问次数。
输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。
输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。
输出格式
对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。
样例 #1
样例输入 #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
样例 #2
样例输入 #2
见附件中的 string/string2.in。
样例输出 #2
见附件中的 string/string2.ans。
样例 #3
样例输入 #3
见附件中的 string/string3.in。
样例输出 #3
见附件中的 string/string3.ans。
样例 #4
样例输入 #4
见附件中的 string/string4.in。
样例输出 #4
见附件中的 string/string4.ans。
提示
【样例解释 #1】
对于第一组数据的第一组询问： - $l = 1$ 时，$s[i: i + l - 1] = \texttt{a}$，$R(s[i + l: i + 2l - 1]) = \texttt{b}$。 - $l = 2$ 时，$s[i: i + l - 1] = \texttt{ab}$，$R(s[i + l: i + 2l - 1]) = \texttt{ca}$。 - $l = 3$ 时，$s[i: i + l - 1] = \texttt{aba}$，$R(s[i + l: i + 2l - 1]) = \texttt{bac}$。 - $l = 4$ 时，$s[i: i + l - 1] = \texttt{abac}$，$R(s[i + l: i + 2l - 1]) = \texttt{baba}$。
这四种情况中，$s[i: i + l - 1]$ 的字典序均小于 $R(s[i + l: i + 2l - 1])$。因此答案为 $4$。
【样例解释 #2】
该样例数据范围满足测试点 $5$。
【样例解释 #4】
该样例数据范围满足测试点 $24 \sim 25$。
【数据范围】
对于所有测试数据保证：$1 \le t \le 5$，$1 \le n \le 10 ^ 5$，$1 \le q \le 10 ^ 5$，$1 \le i + 2r - 1 \le n $，字符串 $s$ 仅包含小写字母。
| 测试点编号 | $n \le$ | $q \le$ | 特殊性质 |
|---|---|---|---|
| $1$ | $5$ | $5$ | A |
| $2$ | $10$ | $10$ | A |
| $3$ | $20$ | $20$ | A |
| $4$ | $50$ | $50$ | A |
| $5$ | $10^2$ | $10^2$ | A |
| $6$ | $10^3$ | $10^3$ | 无 |
| $7$ | $2,000$ | $2,000$ | 无 |
| $8$ | $3,000$ | $3,000$ | 无 |
| $9$ | $4,000$ | $4,000$ | 无 |
| $10$ | $23,333$ | $23,333$ | A |
| $11$ | $5 \times 10 ^ 4$ | $5 \times 10 ^ 4$ | A |
| $12$ | $75,000$ | $75,000$ | A |
| $13$ | $9 \times 10 ^ 4$ | $9 \times 10 ^ 4$ | A |
| $14$ | $10 ^ 5$ | $10 ^ 5$ | A |
| $15$ | $23,333$ | $23,333$ | B |
| $16$ | $75,000$ | $75,000$ | B |
| $17$ | $9 \times 10 ^ 4$ | $9 \times 10 ^ 4$ | B |
| $18$ | $10 ^ 5$ | $10 ^ 5$ | B |
| $19$ | $23,333$ | $23,333$ | 无 |
| $20$ | $5 \times 10 ^ 4$ | $5 \times 10 ^ 4$ | 无 |
| $21$ | $75,000$ | $75,000$ | 无 |
| $22$ | $9 \times 10 ^ 4$ | $9 \times 10 ^ 4$ | 无 |
| $23$ | $95,000$ | $95,000$ | 无 |
| $24 \sim 25$ | $10 ^ 5$ | $10 ^ 5$ | 无 |
特殊性质 A：保证字符串中仅包含字符 $\texttt{a}$ 和 $\texttt{b}$，且每个字符独立等概率地在 $\texttt{a}$ 和 $\texttt{b}$ 中选择。
特殊性质 B：保证字符串中的相邻字符互不相同。