小 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]$ が与えられたとき、任意の $1\le j<i$ に対して $a[j]=b[j]$ であり、かつ $a[i]<b[i]$ であるような $1\le i\le n$ が存在するとき、かつそのときに限り、$a$ は辞書順で $b$ より小さいと定義します。
これらの定義を知った小 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$ が含まれ、文字列の長さと質問の回数を表します。
2 行目には、長さ $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
注記
1 番目のデータセットの 1 番目の質問について：
- $l=1$ のとき、$s[i:i+l-1]=\mathrm{a},R(s[i+l:i+l+l-1])=\mathrm{b}$ です。
- $l=2$ のとき、$s[i:i+l-1]=\mathrm{ab},R(s[i+l:i+l+l-1])=\mathrm{ca}$ です。
- $l=3$ のとき、$s[i:i+l-1]=\mathrm{aba},R(s[i+l:i+l+l-1])=\mathrm{bac}$ です。
- $l=4$ のとき、$s[i:i+l-1]=\mathrm{abac},R(s[i+l:i+l+l-1])=\mathrm{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$ は小文字のみを含みます。
| テストケース番号 | $n$ | $q$ | 特別な性質 |
|---|---|---|---|
| $1$ | $\le 5$ | $\le 5$ | A |
| $2$ | $\le 10$ | $\le 10$ | |
| $3$ | $\le 20$ | $\le 20$ | |
| $4$ | $\le 50$ | $\le 50$ | |
| $5$ | $\le 10^2$ | $\le 10^2$ | |
| $6$ | $\le 10^3$ | $\le 10^3$ | なし |
| $7$ | $\le 2{,}000$ | $\le 2{,}000$ | |
| $8$ | $\le 3{,}000$ | $\le 3{,}000$ | |
| $9$ | $\le 4{,}000$ | $\le 4{,}000$ | |
| $10$ | $\le 23{,}333$ | $\le 23{,}333$ | A |
| $11$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | |
| $12$ | $\le 75{,}000$ | $\le 75{,}000$ | |
| $13$ | $\le 9\times 10^4$ | $\le 9\times 10^4$ | |
| $14$ | $\le 10^5$ | $\le 10^5$ | |
| $15$ | $\le 23{,}333$ | $\le 23{,}333$ | B |
| $16$ | $\le 75{,}000$ | $\le 75{,}000$ | |
| $17$ | $\le 9\times 10^4$ | $\le 9\times 10^4$ | |
| $18$ | $\le 10^5$ | $\le 10^5$ | |
| $19$ | $\le 23{,}333$ | $\le 23{,}333$ | なし |
| $20$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | |
| $21$ | $\le 75{,}000$ | $\le 75{,}000$ | |
| $22$ | $\le 9\times 10^4$ | $\le 9\times 10^4$ | |
| $23$ | $\le 95{,}000$ | $\le 95{,}000$ | |
| $24$ | $\le 10^5$ | $\le 10^5$ | |
| $25$ |
- 特別な性質 A：文字列が文字
aとbのみを含み、各文字が独立に等確率でaとbから選ばれることが保証されます。 - 特別な性質 B：文字列内の隣り合う文字が互いに異なることが保証されます。