今天我们要决定哪个超级英雄团队是最好的：美国队长队（Team Cap）还是钢铁侠队（Team Iron Man，即 Tony）？

共有 $N$ 名狂热粉丝，每名粉丝必须为他最喜欢的超级英雄团队投票：要么是 ‘C’（代表“Cap”），要么是 ‘T’（代表“Tony”）。

由于美国队长知道他没有获胜的机会，而且他是一个非常诚实的人，他决定进行选举舞弊。他想要作废最少数量的选票。

计票过程进行两次： 按照粉丝索引的递增顺序，排除掉作废的选票。 按照粉丝索引的递减顺序，排除掉作废的选票。

如果在美国队长在计票过程中的任何时刻都没有输给 Tony，那么他就会感到满意（他不需要在任何时候拥有更多的选票，但他绝不能拥有更少的选票）。

当然，没人能糊弄 Tony。他了解美国队长的计划，并且对 $Q$ 个场景感兴趣，即美国队长需要作废多少张选票。一个场景由两个数字 $L$ 和 $R$ 定义，表示只有索引从 $L$ 到 $R$（包含 $L$ 和 $R$）的粉丝将参与投票。

输入格式

第一行包含一个整数 $N$，表示粉丝的数量。 第二行包含一个长度为 $N$ 的字符串，由集合 {'C', 'T'} 中的字符组成，表示每位粉丝的投票。 第三行包含一个整数 $Q$，表示场景的数量。 接下来的 $Q$ 行描述了 $Q$ 个场景，每行包含 $L$ 和 $R$ ($1 \le L \le R \le N$)。

输出格式

输出 $Q$ 行，第 $i$ 行包含第 $i$ 个场景的结果。

子任务

• 子任务 1（28 分）：$1 \le N, Q \le 2\,000$
• 子任务 2（54 分）：$1 \le N, Q \le 70\,000$
• 子任务 3（18 分）：$1 \le N, Q \le 500\,000$

样例

样例输入 1

11
CCCTTTTTTCC
3
1 11
4 9
1 6

样例输出 1

4
6
3

说明

在第一个场景中，选票情况为："CCCTTTTTTCC"。 唯一的解决方案是作废 4 张 Tony 的选票。

在第二个场景中，选票情况为："TTTTTT"。 唯一的解决方案是作废所有选票。

在最后一个场景中，选票情况为："CCCTTT"。 唯一的解决方案是作废所有 Tony 的选票。