Description

有 $n$ 块正方体积木，每块积木的颜色是 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 二者之一。第 $i$ 块积木的边长为 $i$。

定义一座塔是合法的，当且仅当：

• 相邻的两个积木块的颜色不同；
• 从下到上，积木块的边长严格递减。

$q$ 次独立询问，每次询问给定 $l,r$，求出：如果用边长 $l,\ldots,r$ 的积木搭塔，至少要搭几座塔。

Input Format

第一行，两个正整数 $n,q$（$1\le n,q\le 10^5$）。

第二行，一个长度为 $n$ 的字符串 $s$。$s_i=\texttt{C}$，表示边长为 $i$ 的积木为 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}$ 色；否则 $s_i=\texttt{P}$，表示边长为 $i$ 的积木为 $\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 色。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$（$1\le l_i\le r_i\le n$），描述一次询问。

Output Format

输出 $q$ 行，第 $i$ 行一个正整数，描述第 $i$ 个询问的答案。

7 4
PPCPPCC
1 7
1 5
3 7
4 5

3
3
2
2

6 2
CCCCCC
1 6
2 5

6
4

16 1
PPPCPCCCCCCPPPPP
1 16

6

Hint

样例解释

样例二解释：所有积木都是 $\colorbox{#e82548}{\textcolor{white}{\textsf{红}}}$ 色的，所以只能搭出仅包含一块积木的塔。显然对于一次询问 $l,r$ 的答案为 $r-l+1$。

子任务

• $\text{Subtask 1 (23 pts)}$：$n,q\le 10$；
• $\text{Subtask 2 (38 pts)}$：$n,q\le 1000$；
• $\text{Subtask 3 (25 pts)}$：至多有 $20$ 块 $\colorbox{87b3ed}{\textcolor{white}{\textsf{蓝}}}$ 色积木。
• $\text{Subtask 4 (24 pts)}$：无额外限制。