小 Y 是一名大學生，最近正在研究字串方向的問題。

小 Y 了解到關於字串的如下定義：

• 給定一個長度為 $n$ 的字串 $s[1:n]$，我們定義其子字串 $s[l:r]\ (1\le l\le r\le n)$ 為選擇 $s[l],s[l+1],\cdots,s[r]$，將其依序串接得到的新字串。
• 給定一個長度為 $n$ 的字串 $s[1:n]$，我們定義其翻轉後的結果 $R(s)$ 為將 $s[n],s[n-1],\cdots,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：保證字串中的相鄰字元互不相同。