Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. AB-обмен
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$n$$$, состоящая из символов $$$\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$$$, так как для каждого индекса операция может быть выполнена не более одного раза.