小 Y 係一名大學生，最近正研究字串方面嘅問題。

小 Y 了解到以下關於字串嘅定義：

• 畀定一個長度為 $n$ 嘅字串 $s[1:n]$，我哋定義佢嘅子字串 $s[l:r]$（$1\le l\le r\le n$）為揀出 $s[l],s[l+1],\ldots,s[r]$，將佢哋順次串接而成嘅新字串。
• 畀定一個長度為 $n$ 嘅字串 $s[1:n]$，我哋定義佢反轉之後嘅結果 $R(s)$ 為將 $s[n],s[n-1],\ldots,s[1]$ 順次串接，即係將字串倒序串接而成嘅字串。
• 畀定兩個長度都係 $n$ 嘅字串 $a[1:n],b[1:n]$，我哋定義 $a$ 嘅字典序細過 $b$，若且唯若存在 $1\le i\le n$，令任意 $1\le j<i$ 都滿足 $a[j]=b[j]$，而且 $a[i]<b[i]$。

了解咗以上定義之後，小 Y 諗到以下問題：

畀定一個長度為 $n$ 嘅字串 $s[1: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$，代表字串長度同查詢次數。

輸入第二行包含一個長度為 $n$、只包含小寫字母嘅字串 $s$。

輸入接落嚟 $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\sim 25$。

資料範圍

對於所有測試資料，保證：$1\le t\le 5$，$1\le n\le 10^5$，$1\le q\le 10^5$，$1\le i+2r-1\le n$，字串 $s$ 只包含小寫字母。

• 特別性質 A：保證字串只包含字元 a 同 b，而且每個字元都獨立、等概率噉喺 a 同 b 入面揀。
• 特別性質 B：保證字串入面相鄰嘅字元互不相同。