题目描述

考虑一个只包含字符 A、B 和 C 的字符串 $t$。我们可以对它进行以下操作：

• 选择任意一个子串 $t[l:r]$ 和字符的任意排列 $(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。

Alina 喜欢所有字符都相同的字符串。她认为字符串 $t$ 的美丽程度是使其所有字符相等所需的最小操作次数。

给定一个长度为 $N$ 的字符串 $S$，由字符 A、B 和 C 组成。回答 $Q$ 个查询。第 $i$ 个查询如下：

• 给定整数 $L_i$ 和 $R_i$，找到子串 $t=S[L_i:R_i]$ 的美丽程度。

约束条件

• $1 \le N \le 10^5$
• $S$ 是长度为 $N$ 的字符串，由字符 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。