Bessie は最近絵を描く道具一式をもらい、牧草地の端にある長い柵を塗りたいと思っています。柵は連続する $N$ 個の長さ 1 メートルの区画からなります（$1\le N\le 10^5$）。Bessie には 26 種類の色があり、明るい色から暗い色へ順に文字 'A' から 'Z' を付けています（'A' はとても明るく、'Z' はとても暗い色です）。したがって、各区画を塗りたい色を、各文字がアルファベットである長さ $N$ の文字列で表せます。

最初はすべての区画に色が付いていません。Bessie は、暗い色の上に明るい色を塗らない限り、任意の連続する区画を一筆で一つの色に塗れます（明るい色の上には暗い色だけを塗れます）。

例えば、最初は無色の長さ四の区画は次のように塗れます。

.... -> BBB. -> BBLL -> BQQL

時間が足りないため、Bessie は連続する区間を塗らずに残す必要があるかもしれないと考えています！現在、$Q$ 個の候補区間（$1\le Q\le 10^5$）を検討しています。それぞれは二つの整数 $(a,b)$ で表され、$1 \leq a \leq b \leq N$ を満たし、塗らずに残す区画の範囲 $a \ldots b$ の両端の番号を指定します。

各候補区間について、その内側のすべての区画を無色のまま残し、外側のすべての区画を希望の色に塗るには、最低何回の筆塗りが必要ですか？この過程で Bessie は実際には塗らないため、各候補区間の答えは独立していることに注意してください。

入力

最初の行には $N$ と $Q$ が与えられます。

次の行には、各区画の希望の色を表す長さ $N$ の文字列が与えられます。

続く $Q$ 行にはそれぞれ空白で区切られた二つの整数 $a$ と $b$ が与えられ、塗らずに残す可能性のある候補区間を表します。

出力

$Q$ 個の候補それぞれについて、答えを一行に出力してください。

入出力例

入力 1

8 2
ABBAABCB
3 6
1 4

出力 1

4
3

注記

この例では、希望の模様 $\texttt{BAAB}$ に対応する部分区間を除くと四回の筆塗りが必要ですが、$\texttt{ABBA}$ を除くと三回だけで済みます。

.... -> AA.. -> ABBB -> ABCB

小課題

• テストケース 1–4 は $N,Q\le 100$ を満たします。
• テストケース 5–7 は $N,Q\le 5000$ を満たします。
• テストケース 8–13 に追加の制約はありません。

問題の作成者：Andi Qu と Brian Dean