You are given a string S, each character of which is either $\verb+N+$ or $\verb+P+.$ In one move, you can perform the following operation:

Pick an index 1 ≤ i ≤ |S| and flip S_{i}, i.e, if $S_{i} = \verb+N+$ set it to $\verb+P+$ and vice versa.

Find the minimum number of moves required to obtain a string such that there exists a way to split it into several continuous substrings, each of which is either $\verb+P+$ or $\verb+NP+$, and the number of $\verb+P+$ substrings in this splitting equals the number of $\verb+NP+$ substrings.

For example$, \verb+NPP+$ and $\verb+PNPPNP+$ can be split this way (into $\verb+NP+ + \verb+P+$ and $\verb+P+ + \verb+NP+ + \verb+P+ + \verb+NP+ respectively) but \verb+NNPP+$ cannot.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first and only line of input of each test case contains the string S.

------ Output Format ------

For each test case, output a single line containing one integer — the minimum number of moves required to transform the string into the desired form.

------ Constraints ------

$1 ≤ T ≤ 3.5 \cdot 10^{4}$
$3 ≤ |S| ≤ 10^{5}$
$S$ contains only characters $\verb+N+$ and $\verb+P+$
$|S|$ is a multiple of $3$
- Sum of $|S|$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------
3
NNN
PNP
NPNPNPNNP

----- Sample Output 1 ------
2
0
2
----- explanation 1 ------
Test Case $1$: Flip the second and third characters so that the string becomes $\verb+NPP+$, which can be broken into substrings $\verb+NP+$ + $\verb+P+$. Here the count of substrings of both types is $1$.

Test Case $2$: The original string can already be split into $\verb+P+$ + $\verb+NP+$, so no more moves are required.

Test Case $3$: Flip the first and eighth characters so that the string becomes $\verb+PPNPNPNPP+$, which can be broken into substrings $\verb+P+$ + $\verb+P+$ + $\verb+NP+$ + $\verb+NP+$ + $\verb+NP+$ + $\verb+P+$. Here the count of substrings of both types is $3$.

见题面

见题面