小 Y — студент университета, который в последнее время исследует задачи о строках.

小 Y познакомился со следующими определениями:

• Для строки $s[1:n]$ длины $n$ её подстрокой $s[l:r]$ ($1\le l\le r\le n$) называется новая строка, полученная последовательным соединением $s[l],s[l+1],\ldots,s[r]$.
• Для строки $s[1:n]$ длины $n$ результат её разворота $R(s)$ — строка, полученная последовательным соединением $s[n],s[n-1],\ldots,s[1]$, то есть символов исходной строки в обратном порядке.
• Для двух строк $a[1:n],b[1:n]$ одинаковой длины $n$ строка $a$ лексикографически меньше $b$ тогда и только тогда, когда существует $1\le i\le n$, такое что для всех $1\le j<i$ выполняется $a[j]=b[j]$ и при этом $a[i]<b[i]$.

Узнав эти определения, 小 Y придумал следующую задачу:

Дана строка $s[1:n]$ длины $n$. Есть $q$ запросов, в каждом заданы два параметра $i,r$. Нужно найти количество значений $l$, удовлетворяющих условиям:

• $1\le l\le r$.
• $s[i:i+l-1]$ лексикографически меньше $R(s[i+l:i+2l-1])$.

小 Y просит вас помочь решить эту задачу.

Входные данные

Данные считываются из файла string.in.

В задаче несколько наборов тестовых данных.

Первая строка содержит два целых числа $c,t$ — номер теста и количество наборов данных соответственно. Значение $c=0$ означает, что тест является примером.

Далее последовательно вводятся все наборы данных. Для каждого набора:

Первая строка содержит два положительных целых числа $n,q$ — длину строки и количество запросов.

Вторая строка содержит строку $s$ длины $n$, состоящую только из строчных букв.

В следующих $q$ строках содержатся по два положительных целых числа $i,r$, описывающих один запрос. Гарантируется $i+2r-1\le n$.

Выходные данные

Выведите результат в файл string.out.

Для каждого запроса в каждом наборе данных выведите одну строку с целым числом — количеством значений $l$, удовлетворяющих условиям.

Примеры

Входные данные 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

Примечание

Рассмотрим первый запрос первого набора данных:

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

Во всех четырёх случаях $s[i:i+l-1]$ лексикографически меньше $R(s[i+l:i+2l-1])$, поэтому ответ равен $4$.

Пример 2

См. файлы string/string2.in и string/string2.ans в каталоге участника.

Ограничения этого примера соответствуют тесту $5$.

Пример 3

См. файлы string/string3.in и string/string3.ans в каталоге участника.

Пример 4

См. файлы string/string4.in и string/string4.ans в каталоге участника.

Ограничения этого примера соответствуют тестам $24\sim25$.

Ограничения

Для всех наборов данных гарантируется: $1\le t\le5$, $1\le n\le10^5$, $1\le q\le10^5$, $1\le i+2r-1\le n$; строка $s$ содержит только строчные буквы.

• Особое свойство $A$: гарантируется, что строка содержит только символы a и b, причём каждый символ выбирается из a и b независимо и равновероятно.
• Особое свойство $B$: гарантируется, что любые соседние символы строки различны.