问题描述

小洞是个字符串爱好者，但今天，他累了，所以这道题目的字符串将仅包含 A 和 B。

当然只是要求 f(S) 未免过于简单，小洞会询问你 Q 次，每次询问一对数 (l, r), 将 Sl 到 Sr 中所有A 改成 B, 所有 B 改成 A, 在每次修改之后你需要求出 f( ′B′ + S +′ A′ )

同样的，小洞还是个排序爱好者，但今天，他累了，所以这道题中你直能通过同时将串中所有形同BA 的子串同时替换为 AB 来进行排序，例如BBA替换一次BA变为BAB，再替换一次变为ABB。

小洞有一个字符串 S = S0S2 . . . Sn−1, 他定义 f(S) 为使用上述方式替换 BA 使得 S 变 为 一 个排 好 序 的 串 所 需要的最小次数，例如f(BBA)=2，f(BABA)=2。

Input

一行一个整数 n, 表示字符串长度。

第二行一个长度为 n 的字符串 S，其中仅包含大写字母 A 和 B, 下标从 0 开始。

第三行一个整数 Q 表示询问次数。

接下来 Q 行，每行两个整数 l, r

Output

输出 Q 行，每行为对应修改后的 f( ′B′ + S +′ A′ )

Examples

输入样例1:

5 

BAABA 

2 

1 3 

0 2

输出样例1:

6
6

输入样例2:

1 

A 

2 

0 0 

0 0

输出样例2:

2
2

Notes

对 20% 的数据，n, Q ≤ 10

对 40% 的数据，n, Q ≤ 5000

对另外 10% 的数据，n ≤ 100, Q ≤ 2 × 105

对 100% 的数据，n, Q ≤ 2 × 105 , 0 ≤ li , ri < n, |S| = n