You are the proud owner of $n$ teddy bears, which are arranged in a row on a shelf. Each teddy bear is colored either black or pink.

An arrangement of teddy bears is beautiful if all the black teddy bears are to the left of all the pink teddy bears. In other words, there does not exist a pair of indices $(i, j)$ ($1 \leq i \lt j \leq n$) such that the $i$-th teddy bear is pink, and the $j$-th teddy bear is black.

You want to reorder the teddy bears into a beautiful arrangement. You are too short to reach the shelf, but luckily, you can send instructions to a robot to move the teddy bears around. In a single instruction, the robot can:

• Choose an index $i$ ($1 \le i \le n - 2$) and reorder the teddy bears at positions $i$, $i + 1$ and $i + 2$ so that all the black teddy bears are to the left of all the pink teddy bears.

What is the minimum number of instructions needed to reorder the teddy bears?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of teddy bears.

The second line of each test case contains a single string $s$ of length $n$ consisting of characters B and P — the colors of the teddy bears. For each $i$ from $1$ to $n$, the $i$-th teddy bear is colored black if $s_i = \texttt{B}$ and pink if $s_i = \texttt{P}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of instructions needed to reorder the teddy bears.

Note

For the first test case, all the teddy bears are pink. Thus, the arrangement is already beautiful, so the answer is $0$.

For the second test case, all the black teddy bears are to the left of all the pink teddy bears. Thus, the answer is $0$.

For the third test case, we can perform $1$ instruction with $i = 1$.

After the instruction, the sequence of colors changes from $\texttt{PPB}$ to $\texttt{BPP}$, and we are done.

For the fourth test case, we can perform $5$ instructions as follows:

• $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}$