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

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

• 给定一个长度为 $n$ 的字符串 $s[1:n]$，我们定义其子串 $s[l:r]$（$1\le l\le r\le 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\le i\le n$，使得对于任意 $1\le j<i$，$a[j]=b[j]$，且 $a[i]<b[i]$。

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

给定一个长度为 $n$ 的字符串 $s[1:n]$。有 $q$ 次询问，每次询问给定两个参数 $i,r$。你需要求出有多少 $l$，满足如下条件:

• $1\le l\le 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\le n$。

输出格式

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

样例一

input

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

output

4
0
3
2
0
2

explanation

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

• $l=1$ 时，$s[i:i+l-1]=\mathtt{\text{a}}$，$R(s[i+l:i+2l-1])=\mathtt{\text{b}}$。
• $l=2$ 时，$s[i:i+l-1]=\mathtt{\text{ab}}$，$R(s[i+l:i+2l-1])=\mathtt{\text{ca}}$。
• $l=3$ 时，$s[i:i+l-1]=\mathtt{\text{aba}}$，$R(s[i+l:i+2l-1])=\mathtt{\text{bac}}$。
• $l=4$ 时，$s[i:i+l-1]=\mathtt{\text{abac}}$，$R(s[i+l:i+2l-1])=\mathtt{\text{baba}}$。

这四种情况中，$s[i:i+l-1]$ 的字典序均小于 $R(s[i+l:i+2l-1])$。因此答案为 $4$。

样例二

见附件下载。

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

样例三

见附件下载。

样例四

见附件下载。

该样例数据范围满足测试点 $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$ 仅包含小写字母。

特殊性质 A：保证字符串中仅包含字符 $\mathtt{\text{a}}$ 和 $\mathtt{\text{b}}$，且每个字符独立等概率地在 $\mathtt{\text{a}}$ 和 $\mathtt{\text{b}}$ 中选择。

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

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$