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