该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $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$。

输出格式

对于每组测试用例，输出一个整数，表示最多可以进行的操作次数。

输入输出样例

3
2
AB
4
BBBA
4
AABB

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$ 进行操作，因为每个下标最多只能操作一次。