Ryan is a boy from a small town, who has been given a task by his father. He has N wooden planks, numbered from 1 to N, which are colored either black or white.

His task is to color all planks the same color! But there is some magic in the winds of his small town. Whenever he colors the i^{th} ( plank which has the color S_{i} ) to a color P then following events happen:
- if 2 ≤ i ≤ N and S_{i} = S_{i - 1}, then color of (i - 1)^{th} plank changes to P.
- if 1 ≤ i ≤ N - 1 and S_{i} = S_{i + 1}, then color of (i + 1)^{th} plank changes to P.

Now this process continues for the newly colored planks also. If none of the neighbors have same color, then nothing happens to the neighbors.

Suppose Ryan has planks which have their coloring : B B W W W B
If Ryan colors the fourth plank( whose color is W ) to color B, then the finally the planks would be colored as following:

B B B B B B

Ryan can choose any one of the N planks and change its color as many times as he wants. Determine the minimum number of times Ryan has to paint a plank such that all planks get the same color at the end.

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

• First line will contain T, number of testcases. Then the testcases follow.
• The first line of each test case consists of an integer N the number of planks
• Second line of each test case consists of a string S of size N,where the i th character denotes the color of plank i

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

For each testcase, output a single integer denoting the minimum number of times Ryan has to paint a single plank such that all planks get the same color at the end.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
- $S$ consists only of characters $B$ and $W$
- The sum of $N$ over all cases doesn't exceed $10^{5}$.

----- Sample Input 1 ------
4
6
BBWWWB
5
WWBWB
2
BB
9
WWBBBBBWW

----- Sample Output 1 ------
1
2
0
1

----- explanation 1 ------
Test case 1:
The first test case is already described in the question.

Test case 2:
Ryan can paint the third plank to $W$. After doing so the color string of planks become $W W W W B$. Then he can again paint the third plank to the color $B$.
After doing so the string goes through following transitions:
- The color of third plank changes to $B$. ( The string becomes $W W B W B$ )
- The color of second and fourth plank changes to $B$. ( The string becomes $W B B B B$ )
- The color of first plank changes to $B$. ( The string becomes $B B B B B$ )

Finally, all planks have same color.

Test case 3:
All planks have the same color.

Test case 4:
Ryan can paint any of the planks numbered from $3$ to $7$ to $W$, and all these planks will be colored to $W$!

见题面

见题面