给定一个长度为 $$$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$$$ 进行操作,因为我们只能对每个索引最多执行一次操作。