小 Y jest studentem i ostatnio bada problemy dotyczące napisów.

Poznał następujące definicje:

• Dla napisu $s[1:n]$ o długości $n$ jego fragment $s[l:r]$ ($1 \le l \le r \le n$) to nowy napis utworzony przez połączenie kolejno znaków $s[l],s[l+1],\ldots,s[r]$.
• Dla napisu $s[1:n]$ o długości $n$ jego odwrócenie $R(s)$ to połączenie kolejno znaków $s[n],s[n-1],\ldots,s[1]$, czyli napis zapisany w odwrotnej kolejności.
• Dla dwóch napisów $a[1:n],b[1:n]$ o długości $n$ definiujemy, że $a$ jest leksykograficznie mniejsze od $b$ wtedy i tylko wtedy, gdy istnieje $1 \le i \le n$, takie że dla każdego $1 \le j < i$ zachodzi $a[j]=b[j]$ oraz $a[i]<b[i]$.

Po poznaniu tych definicji 小 Y wymyślił następujący problem:

Dany jest napis $s[1:n]$ o długości $n$ oraz $q$ zapytań. Każde zapytanie podaje dwa parametry $i,r$. Należy obliczyć, ile wartości $l$ spełnia następujące warunki:

• $1 \le l \le r$.
• $s[i:i+l-1]$ jest leksykograficznie mniejsze od $R(s[i+l:i+2l-1])$.

小 Y prosi cię o pomoc w rozwiązaniu tego problemu.

Wejście

Dane należy odczytać z pliku string.in.

Zadanie zawiera wiele zestawów danych.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $c,t$, oznaczające numer testu i liczbę zestawów danych. $c=0$ oznacza przykład.

Następnie podane są kolejno zestawy danych. Każdy z nich ma następującą postać:

Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n,q$, oznaczające długość napisu i liczbę zapytań.

Drugi wiersz zawiera napis $s$ o długości $n$, złożony wyłącznie z małych liter.

Każdy z następnych $q$ wierszy zawiera dwie dodatnie liczby całkowite $i,r$, opisujące jedno zapytanie. Zagwarantowano $i+2r-1 \le n$.

Wyjście

Wynik należy zapisać do pliku string.out.

Dla każdego zapytania w każdym zestawie danych wypisz jeden wiersz z jedną liczbą całkowitą: liczbą wartości $l$ spełniających warunki.

Przykład

Wejście 1

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

Wyjście 1

4
0
3
2
0
2

Uwagi

Dla pierwszego zapytania w pierwszym zestawie danych:

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

We wszystkich czterech przypadkach $s[i:i+l-1]$ jest leksykograficznie mniejsze od $R(s[i+l:i+2l-1])$, więc odpowiedź wynosi $4$.

Przykład 2

Zobacz pliki string/string2.in i string/string2.ans w katalogu zawodnika.

Zakres danych tego przykładu spełnia ograniczenia testu 5.

Przykład 3

Zobacz pliki string/string3.in i string/string3.ans w katalogu zawodnika.

Przykład 4

Zobacz pliki string/string4.in i string/string4.ans w katalogu zawodnika.

Zakres danych tego przykładu spełnia ograniczenia testów $24 \sim 25$.

Ograniczenia

Dla wszystkich danych testowych zagwarantowano: $1 \le t \le 5$, $1 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le i+2r-1 \le n$, a napis $s$ zawiera wyłącznie małe litery.

• Właściwość szczególna A: napis zawiera wyłącznie znaki a i b, a każdy znak wybierany jest niezależnie i z jednakowym prawdopodobieństwem spośród a i b.
• Właściwość szczególna B: sąsiednie znaki w napisie są różne.