E. Удивительные Мишки Тедди
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы гордый владелец $$$n$$$ мишек Тедди, которые расположены в ряд на полке. Каждый мишка Тедди окрашен либо в черный, либо в розовый цвет.

Расположение мишек Тедди считается прекрасным, если все черные мишки находятся слева от всех розовых мишек. Другими словами, не существует пары индексов $$$(i, j)$$$ ($$$1 \leq i \lt j \leq n$$$), таких что $$$i$$$-й мишка Тедди розовый, а $$$j$$$-й мишка Тедди черный.

Вы хотите переупорядочить мишек Тедди в прекрасное расположение. Вы слишком низкий, чтобы достать до полки, но, к счастью, вы можете отправить инструкции роботу, чтобы он перемещал мишек. В одной инструкции робот может:

  • Выбрать индекс $$$i$$$ ($$$1 \le i \le n - 2$$$) и переупорядочить мишек Тедди на позициях $$$i$$$, $$$i + 1$$$ и $$$i + 2$$$ так, чтобы все черные мишки были слева от всех розовых мишек.

Какое минимальное количество инструкций необходимо, чтобы переупорядочить мишек Тедди?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество мишек Тедди.

Вторая строка каждого набора содержит одну строку $$$s$$$ длиной $$$n$$$, состоящую из символов B и P — цветов мишек Тедди. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, $$$i$$$-й мишка Тедди окрашена в черный цвет, если $$$s_i = \texttt{B}$$$, и в розовый цвет, если $$$s_i = \texttt{P}$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите одно целое число — минимальное количество инструкций, необходимых для переупорядочивания мишек Тедди.

Пример
Входные данные
5
3
PPP
3
BPP
3
PPB
7
PPBPPBB
15
BPBPBBBBBPBBBBB
Выходные данные
0
0
1
5
14
Примечание

Для первого набора все мишки Тедди розовые. Таким образом, расположение уже прекрасно, поэтому ответ $$$0$$$.

Для второго набора все черные мишки находятся слева от всех розовых мишек. Таким образом, ответ $$$0$$$.

Для третьего набора мы можем выполнить $$$1$$$ инструкцию с $$$i = 1$$$.

После инструкции последовательность цветов изменится с $$$\texttt{PPB}$$$ на $$$\texttt{BPP}$$$, и мы получили прекрасное расположение.

Для четвертого набора мы можем выполнить $$$5$$$ инструкций следующим образом:

  • $$$i = 1$$$: $$$\texttt{}\color{magenta}{\texttt{PPB}}\texttt{PPBB} \rightarrow \texttt{}\color{magenta}{\texttt{BPP}}\texttt{PPBB}$$$
  • $$$i = 5$$$: $$$\texttt{BPPP}\color{magenta}{\texttt{PBB}}\texttt{} \rightarrow \texttt{BPPP}\color{magenta}{\texttt{BBP}}\texttt{}$$$
  • $$$i = 4$$$: $$$\texttt{BPP}\color{magenta}{\texttt{PBB}}\texttt{P} \rightarrow \texttt{BPP}\color{magenta}{\texttt{BBP}}\texttt{P}$$$
  • $$$i = 3$$$: $$$\texttt{BP}\color{magenta}{\texttt{PBB}}\texttt{PP} \rightarrow \texttt{BP}\color{magenta}{\texttt{BBP}}\texttt{PP}$$$
  • $$$i = 2$$$: $$$\texttt{B}\color{magenta}{\texttt{PBB}}\texttt{PPP} \rightarrow \texttt{B}\color{magenta}{\texttt{BBP}}\texttt{PPP}$$$