您是 $$$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 — 泰迪熊的颜色。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,如果 $$$s_i = \texttt{B}$$$,则第 $$$i$$$ 泰迪熊为黑色,如果 $$$s_i = \texttt{P}$$$,则为粉红色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 重新排序泰迪熊所需的最少指令数。
示例
输入复制
53PPP3BPP3PPB7PPBPPBB15BPBPBBBBBPBBBBB
输出复制
0 0 1 5 14
注意
对于第一个测试用例,所有泰迪熊都是粉红色的。这样,排列已经很漂亮了,所以答案是$$$0$$$。
对于第二个测试用例,所有黑色泰迪熊都位于所有粉色泰迪熊的左侧。因此,答案是$$$0$$$。
对于第三个测试用例,我们可以执行 $$$1$$$ 指令,$$$i = 1$$$。
执行指令后,颜色顺序从 $$$\texttt{PPB}$$$ 变为 $$$\texttt{BPP}$$$,我们就完成了。
对于第四个测试用例,我们可以执行$$$5$$$指令,如下所示:
- $$$i = 1$$$: $$$\texttt{}\color{洋红色}{\texttt{PPB}}\texttt{PPBB} \rightarrow \texttt{}\color{洋红色}{\texttt{BPP}}\texttt{PPBB}$$$
- $$$i = 5$$$: $$$\texttt{BPPP}\color{洋红色}{\texttt{PBB}}\texttt{} \rightarrow \texttt{BPPP}\color{洋红色}{\texttt{BBP}}\texttt{}$$$
- $$$i = 4$$$: $$$\texttt{BPP}\color{洋红色}{\texttt{PBB}}\texttt{P} \rightarrow \texttt{BPP}\color{洋红色}{\texttt{BBP}}\texttt{P}$$$
- $$$i = 3$$$: $$$\texttt{BP}\color{洋红色}{\texttt{PBB}}\texttt{PP} \rightarrow \texttt{BP}\color{洋红色}{\texttt{BBP}}\texttt{PP}$$$
- $$$i = 2$$$: $$$\texttt{B}\color{洋红色}{\texttt{PBB}}\texttt{PPP} \rightarrow \texttt{B}\color{洋红色}{\texttt{BBP}}\texttt{PPP}$$$