問題文

文字 A, B, C のみからなる文字列 $t$ を考えます。 これに対し、以下の操作を行えます。

• 任意の部分文字列 t\[l:r\] と文字 $($A$,$B$,$C$)$ の任意の並べ替え $(X, Y, Z)$ を選ぶ。ここで、t\[l:r\] は $t$ の $l$ 文字目から $r$ 文字目までで形成される部分文字列であり、$l$ と $r$ を選べる。そして、t\[l:r\] の各文字 A, B, C をそれぞれ $X$, $Y$, $Z$ で置き換える。

例えば、文字列 $t =$ ACBAAC に対して、部分文字列 t\[3:6\] と $(X,Y,Z)=($C$,$B$,$A$)$ を選べます。 この操作を行うと、文字列は ACBCCA となります。

アリーナは、すべての文字が同じであるような文字列が好きです。彼女は、文字列 $t$ の美しさを、そのすべての文字を同じにするために必要な最小の操作回数と定義します。

長さ $N$ の文字 A, B, C のみからなる文字列 $S$ が与えられます。 $Q$ 個のクエリに答えてください。$i$ 個目のクエリは以下の通りです。

• 整数 $L_i$ と $R_i$ が与えられるので、部分文字列 t=S\[L_i:R_i\] の美しさを求めよ。

制約

• $1 \\le N \\le 10^5$
• $S$ は文字 A, B, C のみからなる文字列である。
• $1 \\le Q \\le 10^5$
• $1 \\le L_i \\le R_i \\le N$
• 入力中のすべての数は整数である。

入力

入力は標準入力から以下の形式で与えられる。

$N$ $Q$ $S$ $L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_Q$ $R_Q$

出力

$Q$ 行を出力せよ。$i$ 行目には、$i$ 個目のクエリへの答えを出力せよ。

入力例 1

6 4
ABCCCA
3 5
2 3
1 3
1 6

出力例 1

0
1
2
2

一つ目のクエリでは、文字列は $t =$ CCC であり、すでにすべての文字が同じです。答えは $0$ となります。

二つ目のクエリでは、文字列は $t =$ BC です。これは、部分文字列 t\[2:2\] と $(X,Y,Z)=($A$,$C$,$B$)$ を選ぶことで、一回の操作で BB に変えることができます。

三つ目のクエリでは、文字列は $t =$ ABC です。これは、部分文字列 t\[2:3\] と $(X,Y,Z)=($C$,$A$,$B$)$ を選ぶことで、一回の操作で AAB に、続いて部分文字列 t\[1:2\] と $(X,Y,Z)=($B$,$A$,$C$)$ を選ぶことで、二回目の操作で BBB に変えることができます。