CF1896B.AB Flipping

You are given a string $s$ of length $n$ consisting of characters $\texttt{A}$ and $\texttt{B}$. You are allowed to do the following operation:

• Choose an index $1 \le i \le n - 1$ such that $s_i = \texttt{A}$ and $s_{i + 1} = \texttt{B}$. Then, swap $s_i$ and $s_{i+1}$.

You are only allowed to do the operation at most once for each index $1 \le i \le n - 1$. However, you can do it in any order you want. Find the maximum number of operations that you can carry out.

给你一个长度为 $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$，你最多只能执行一次该操作。但你可以按任意顺序执行这些操作。求你能执行的操作的最大次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2\cdot 10^5$) — the length of string $s$.

The second line of each test case contains the string $s$ ($s_i=\texttt{A}$ or $s_i=\texttt{B}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

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

每个测试用例的第二行包含字符串 $s$（其中每个字符 $s_i$ 为 $\texttt{A}$ 或 $\texttt{B}$）。

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

For each test case, print a single integer containing the maximum number of operations that you can carry out.

对于每个测试用例，输出一个整数，表示你能执行的最大操作次数。

In the first test case, we can do the operation exactly once for $i=1$ as $s_1=\texttt{A}$ and $s_2=\texttt{B}$.

In the second test case, it can be proven that it is not possible to do an operation.

In the third test case, we can do an operation on $i=2$ to form $\texttt{ABAB}$, then another operation on $i=3$ to form $\texttt{ABBA}$, and finally another operation on $i=1$ to form $\texttt{BABA}$. Note that even though at the end, $s_2 = \texttt{A}$ and $s_3 = \texttt{B}$, we cannot do an operation on $i=2$ again as we can only do the operation at most once for each index.

在第一个测试用例中，我们可以恰好对 $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$ 执行操作，因为每个下标最多只能执行一次操作。