Дана строка $$$s$$$ длины $$$n$$$, состоящая из символов $$$\texttt{A}$$$ и $$$\texttt{B}$$$. Вам разрешено выполнять следующую операцию:
Для каждого индекса $$$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$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которое можно выполнить.
32AB4BBBA4AABB
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$$$, так как для каждого индекса операция может быть выполнена не более одного раза.
