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]=\texttt{a}$ ו־$R(s[i+l:i+l+l-1])=\texttt{b}$.
• כאשר $l=2$, מתקיים $s[i:i+l-1]=\texttt{ab}$ ו־$R(s[i+l:i+l+l-1])=\texttt{ca}$.
• כאשר $l=3$, מתקיים $s[i:i+l-1]=\texttt{aba}$ ו־$R(s[i+l:i+l+l-1])=\texttt{bac}$.
• כאשר $l=4$, מתקיים $s[i:i+l-1]=\texttt{abac}$ ו־$R(s[i+l:i+l+l-1])=\texttt{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: מובטח שכל שני תווים סמוכים במחרוזת שונים זה מזה.