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$, для якого $a[j]=b[j]$ для всіх $1\le j<i$ та $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]=a$, $R(s[i+l:i+l+l-1])=b$.
• За $l=2$ маємо $s[i:i+l-1]=ab$, $R(s[i+l:i+l+l-1])=ca$.
• За $l=3$ маємо $s[i:i+l-1]=aba$, $R(s[i+l:i+l+l-1])=bac$.
• За $l=4$ маємо $s[i:i+l-1]=abac$, $R(s[i+l:i+l+l-1])=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: будь-які сусідні символи рядка різні.