题目描述

$sly$ 做了一个奇怪的梦，梦里他站在一朵云上，面前有一个个通往天空的石阶和一块石碑。石阶有两个颜色，白色和黑色。石碑上面记录了一些问题，需要正确回答所有问题才能通过石阶抵达天空之上。$sly$ 很想去天空之上看看，他能一次上两个台阶或者上一个台阶，想你帮助他回答这些问题。

$sly$ 发现石碑上的问题有两个关键信息 $x, y$ 问题表示为走到第 $x$ 级石阶至少走多少颜色为 $y$ 的石阶。

输入格式

第一行一个整数 $n$（$1 \leq n \le 2 \times 10^5$ ） 表示石阶的数量。

第二行一个长度为 $n$ 的字符串 $s$ 表示石阶的颜色。

第三行一个整数 $q$（$1 \leq q \le 2 \times 10^5$ ） 表示询问的数量。

接下来 $q$ 行，每行一个整数 $x$（$1\le x \leq n$），一个字符 $y$（$y \in \{ B,W \}$）表示询问。

数据保证 $s$ 只包含 $\{B,W \}$ 。

输出格式

输出 $q$ 行，每行一个正整数表示答案。

输入样例

7
BBBWBWB
5
4 B
1 W
6 W
6 B
3 B

输出样例

1
0
1
1
2

样例解释

蓝色代表走的石阶。