该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在王洋老师的精密谋划下，贾府成功渡过难关，化险为夷。 为了庆祝新生，同时也是为了迎接即将到来的圣驾，贾政下令对在动荡中斑驳的大观园长墙进行重新粉刷。正当众人为浩大的工程量发愁时，王洋老师敏锐地察觉到，只要完成这最后一次统筹规划，时空的裂隙就会打开，他就能穿越回 2026 年的机房！为了赶时间，部分被假山遮挡的墙段可以选择不刷。 王洋老师立刻接管了工匠的指挥权，开始计算在保留不同未粉刷区段的情况下，最少需要多少笔墨才能完成这幅宏大的画卷。

题目描述

大观园的墙壁由$N$个连续的 1 米长的区段组成（$1 \le N \le 10^5$）。 工匠们有 26 种不同深浅的颜料，分别用大写字母 'A' 到 'Z' 表示（'A' 最浅，'Z' 最深）。 期望的粉刷图案可以用一个长度为$N$的字符串表示。最初，所有的墙壁区段都是空白的。 工匠每一笔可以粉刷任意长度的连续区段，但有一个严格的规则：只能用较深的颜色覆盖较浅的颜色（即不能将浅色涂在深色上）。

例如，一个初始为空白的长度为 4 的墙段可以这样粉刷：.... -> BBB. -> BBLL -> BQQL由于时间紧迫，王洋老师考虑留下一些连续的区段不粉刷。 他有$Q$个候选方案（$1 \le Q \le 10^5$），每个方案由两个整数$a$和$b$描述（$1 \le a \le b \le N$），表示区间$[a, b]$内的墙段将被留白不涂。对于每一个候选方案，如果不粉刷$[a, b]$区间内的墙段，而要将区间外的所有墙段粉刷成期望的颜色，最少需要多少次涂刷动作？（注意：王洋老师只是在做推演评估，每次查询之间是相互独立的）。

输入格式

第一行包含两个整数$N$和$Q$。 第二行包含一个长度为$N$的字符串，表示墙壁每个区段期望的最终颜色。 接下来的$Q$行，每行包含两个空格分隔的整数$a$和$b$，表示一个候选的留白区间。

输出格式

对于$Q$个候选方案中的每一个，在新的一行输出最少的涂刷次数。

样例输入

8 2
ABBAABCB
3 6
1 4

样例输出

4
3

提示

在样例中，排除了期望图案 对应的子区间后（即查询 3 6），粉刷剩余部分最少需要四笔；而排除 （即查询 1 4）后，最少只需要三笔：BAABABBA.... -> AA.. -> ABBB -> ABCB数据范围：对于测试点 1-4，满足$N, Q \le 100$。对于测试点 5-7，满足$N, Q \le 5000$。对于测试点 8-13，无额外限制。