← 返回题目列表

Codeforces · 1896/B

B. AB 翻转

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 $$$\texttt{A}$$$ 和 $$$\texttt{B}$$$ 组成。您可以进行以下操作:

- 选择索引 $$$1 \le i \le n - 1$$$,使得 $$$s_i = \texttt{A}$$$ 和 $$$s_{i + 1} = \texttt{B}$$$。然后,交换 $$$s_i$$$ 和 $$$s_{i+1}$$$。

每个索引 $$$1 \le i \le n - 1$$$ 最多只能执行一次操作。但是,您可以按照您想要的任何顺序进行操作。找出您可以执行的最大操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含字符串 $$$s$$$ ($$$s_i=\texttt{A}$$$ 或 $$$s_i=\texttt{B}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印一个包含可以执行的最大操作数的整数。

示例

输入 #1

3
2
AB
4
BBBA
4
AABB

输出 #1

1
0
3

注意

在第一个测试用例中,我们可以对 $$$i=1$$$ 执行一次操作,如 $$$s_1=\texttt{A}$$$ 和 $$$s_2=\texttt{B}$$$。

在第二个测试用例中,可以证明无法进行操作。

在第三个测试用例中,我们可以对$$$i=2$$$进行一次操作,形成$$$\texttt{ABAB}$$$,然后对$$$i=3$$$进行一次操作,形成$$$\texttt{ABBA}$$$,最后对$$$i=1$$$进行一次操作,形成$$$\texttt{BABA}$$$。请注意,即使最后 $$$s_2 = \texttt{A}$$$ 和 $$$s_3 = \texttt{B}$$$,我们也无法再次对 $$$i=2$$$ 进行操作,因为我们只能对每个索引最多执行一次操作。