你拥有 n 只泰迪熊，它们排成一排摆放在架子上。每只泰迪熊的颜色为黑色或粉色。

如果所有黑色泰迪熊都在所有粉色泰迪熊的左侧，那么这个泰迪熊排列方式就是美观的。换句话说，不存在满足 1 ≤ i < j ≤ n 的下标对 (i, j)，使得第 i 只泰迪熊是粉色，而第 j 只泰迪熊是黑色。

你想将这些泰迪熊重新排列成美观的样式。你个子太矮够不到架子，但幸运的是，你可以给机器人下达指令来移动泰迪熊。在单条指令中，机器人可以：

• 选择一个下标 i（1 ≤ i ≤ n - 2），将位置 i、i+1、i+2 处的泰迪熊重新排序，使所有黑色泰迪熊都位于所有粉色泰迪熊的左侧。

请问将泰迪熊重新排列成美观样式，最少需要多少条指令？

输入

每组测试包含多组用例。第一行输入用例数量 t（1 ≤ t ≤ 10⁴）。 每个用例的第一行输入一个整数 n（3 ≤ n ≤ 2·10⁵）——泰迪熊的数量。 每个用例的第二行输入一个长度为 n 的字符串 s，由字符 B 和 P 组成——代表泰迪熊的颜色。对于 1 到 n 的每个下标 i，若 sᵢ = 'B'，则第 i 只泰迪熊为黑色；若 sᵢ = 'P'，则为粉色。 保证所有用例的 n 之和不超过 2·10⁵。

输出

对于每个用例，输出一个整数——所需的最少指令数。

5
3
PPP
3
BPP
3
PPB
7
PPBPPBB
15
BPBPBBBBBPBBBBB

0
0
1
5
14

说明

第一个用例：所有泰迪熊都是粉色，因此排列已经是美观的，答案为 0。 第二个用例：所有黑色泰迪熊都在粉色泰迪熊左侧，因此答案为 0。 第三个用例：对下标 i=1 执行 1 条指令即可。 执行指令后，颜色序列从 PPB 变为 BPP，完成排序。 第四个用例：可以按如下方式执行 5 条指令：

• i=1：PPBPPBB → BPPPPBB
• i=5：BPPPPBB → BPPPBBP
• i=4：BPPPBBP → BPPBBPP
• i=3：BPPBBPP → BPBBPPP
• i=2：BPBBPPP → BBBPPPP