有 $N$ 名选民排成一列，编号从 $1$ 到 $N$。他们正在 Alice 和 Bob 两位候选人之间进行投票。他们将按 $1$ 到 $N$ 的顺序依次投票，每人投给 Alice 或 Bob。

选民的偏好由字符串 $S$ 表示：若第 $i$ 位选民原本打算投给 Alice，则 $S_i = A$；若原本打算投给 Bob，则 $S_i = B$。

你想要操纵选举结果，使 Alice 获胜。为此，你获得了一种特殊能力：你可以说服人们改变立场，成为“多数派选民”。编号为 $X$ 的多数派选民会投给当前票数严格领先的候选人（根据前 $1$ 到 $X-1$ 位选民的投票结果）。如果两位候选人票数相等，多数派选民将不会投出任何票。

当且仅当 Alice 获得的票数严格多于 Bob 时，Alice 赢得选举。

令 $f(S)$ 表示为了让 Alice 赢得选举，你最少需要将多少人转变为多数派选民。如果无论如何 Alice 都无法获胜，则 $f(S) = -1$。

现在，给定一个长度为 $N$ 的二进制字符串 $S$，以及 $Q$ 次查询，格式如下： * 给定 $L$ 和 $R$，求 $f(S[L, R])$，其中 $S[L, R]$ 表示子串 $S_L S_{L+1} \dots S_R$。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含多行输入：
  • 第一行包含两个整数 $N$ 和 $Q$，分别表示字符串长度和查询次数。
  • 第二行包含一个长度为 $N$ 的二进制字符串 $S$。
  • 接下来的 $Q$ 行，每行包含两个整数 $L$ 和 $R$，表示每次查询的参数。

输出格式

对于每个测试用例，针对每次查询，输出一行 $f(S[L, R])$ 的值。

数据范围

• $1 \le T \le 10^4$
• $1 \le N, Q \le 2 \cdot 10^5$
• $S_i \in \{A, B\}$
• $|S| = N$
• $1 \le L \le R \le N$
• $N$ 的总和与 $Q$ 的总和均不超过 $2 \cdot 10^5$

样例

样例输入 1

2
4 4
AABA
1 4
2 3
3 3
3 4
5 2
BBBBA
1 5
5 5

样例输出 1

0
1
-1
1
4
0

说明

测试用例 1：以下是各次查询的解释。

• 查询 1：Alice 已经获胜，因为她有 3 票，而 Bob 只有 1 票。
• 查询 2：Alice 和 Bob 各有 1 票。如果你将该 Bob 选民改为多数派选民，Alice 最终会获胜，因为该多数派选民也会投给 Alice（因为前一位选民投给了 Alice）。
• 查询 3：你所能做的最好情况是将唯一的 Bob 选民改为多数派选民，他将不会投给任何人；但这不足以让 Alice 获胜。因此，答案为 $-1$。
• 查询 4：Alice 和 Bob 各有一票。将唯一的 Bob 选民改为多数派选民将导致 Alice 获胜，因为该多数派选民不会投给任何人，而 Alice 仍有一票。