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