小 Y ist Student und beschäftigt sich zurzeit mit Problemen über Zeichenketten.

小 Y hat die folgenden Definitionen kennengelernt:

• Für eine Zeichenkette $s[1:n]$ der Länge $n$ definieren wir die Teilzeichenkette $s[l:r]$ mit $1\le l\le r\le n$ als die Zeichenkette, die durch Aneinanderhängen von $s[l],s[l+1],\ldots,s[r]$ in dieser Reihenfolge entsteht.
• Für eine Zeichenkette $s[1:n]$ der Länge $n$ ist ihre Umkehrung $R(s)$ die Zeichenkette, die durch Aneinanderhängen von $s[n],s[n-1],\ldots,s[1]$ entsteht, also durch Umkehren der Zeichenreihenfolge.
• Für zwei Zeichenketten $a[1:n],b[1:n]$ gleicher Länge $n$ ist $a$ genau dann lexikografisch kleiner als $b$, wenn ein $1\le i\le n$ existiert, sodass für alle $1\le j<i$ die Gleichheit $a[j]=b[j]$ gilt und zugleich $a[i]<b[i]$.

Nach diesen Definitionen ist 小 Y auf das folgende Problem gekommen:

Gegeben ist eine Zeichenkette $s[1:n]$ der Länge $n$. Es gibt $q$ Anfragen, von denen jede zwei Parameter $i,r$ angibt. Du sollst bestimmen, wie viele Werte $l$ die folgenden Bedingungen erfüllen:

• $1\le l\le r$.
• $s[i:i+l-1]$ ist lexikografisch kleiner als $R(s[i+l:i+2l-1])$.

小 Y bittet dich, ihm bei diesem Problem zu helfen.

Eingabe

Lies die Daten aus der Datei string.in.

Diese Aufgabe enthält mehrere Testfälle.

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $c,t$: die Testfallnummer und die Anzahl der Testfälle. $c=0$ bedeutet, dass es sich um ein Beispiel handelt.

Anschließend werden die Testfälle der Reihe nach eingegeben. Für jeden Testfall gilt:

Die erste Zeile enthält zwei positive ganze Zahlen $n,q$, die Länge der Zeichenkette und die Anzahl der Anfragen.

Die zweite Zeile enthält eine Zeichenkette $s$ der Länge $n$, die nur aus Kleinbuchstaben besteht.

Die folgenden $q$ Zeilen enthalten jeweils zwei positive ganze Zahlen $i,r$, die eine Anfrage angeben. Es ist garantiert, dass $i+2r-1\le n$ gilt.

Ausgabe

Schreibe die Ausgabe in die Datei string.out.

Gib für jede Anfrage jedes Testfalls eine Zeile mit einer ganzen Zahl aus: der Anzahl der Werte $l$, die die Bedingungen erfüllen.

Beispiele

Eingabe 1

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

Ausgabe 1

4
0
3
2
0
2

Hinweis zu Beispiel 1

Für die erste Anfrage des ersten Testfalls gilt:

• Für $l=1$: $s[i:i+l-1]=\mathrm{a}$, $R(s[i+l:i+l+l-1])=\mathrm{b}$.
• Für $l=2$: $s[i:i+l-1]=\mathrm{ab}$, $R(s[i+l:i+l+l-1])=\mathrm{ca}$.
• Für $l=3$: $s[i:i+l-1]=\mathrm{aba}$, $R(s[i+l:i+l+l-1])=\mathrm{bac}$.
• Für $l=4$: $s[i:i+l-1]=\mathrm{abac}$, $R(s[i+l:i+l+l-1])=\mathrm{baba}$.

In allen vier Fällen ist $s[i:i+l-1]$ lexikografisch kleiner als $R(s[i+l:i+2l-1])$. Daher ist die Antwort $4$.

Beispiel 2

Siehe string/string2.in und string/string2.ans im Teilnehmerverzeichnis.

Der Wertebereich dieses Beispiels erfüllt die Beschränkungen von Testfall $5$.

Beispiel 3

Siehe string/string3.in und string/string3.ans im Teilnehmerverzeichnis.

Beispiel 4

Siehe string/string4.in und string/string4.ans im Teilnehmerverzeichnis.

Der Wertebereich dieses Beispiels erfüllt die Beschränkungen der Testfälle $24\sim25$.

Beschränkungen

Für alle Testdaten gilt garantiert $1\le t\le5$, $1\le n\le10^5$, $1\le q\le10^5$, $1\le i+2r-1\le n$. Die Zeichenkette $s$ enthält nur Kleinbuchstaben.

• Besondere Eigenschaft A: Die Zeichenkette enthält garantiert nur die Zeichen a und b. Jedes Zeichen wird unabhängig und mit gleicher Wahrscheinlichkeit aus a und b gewählt.
• Besondere Eigenschaft B: Benachbarte Zeichen der Zeichenkette sind garantiert verschieden.