A93162.「NOI2023」字符串

小 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 想求助你帮忙解决这一问题。

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

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

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

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

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

输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。

输出到文件 string.out 中。

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

对于所有测试数据保证：$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：保证字符串中的相邻字符互不相同。