Magical Planks

 Ryan is a boy from, who has been given a task by his father. He has 

N$N$ wooden planks, numbered from 1$1$ to N$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 ith$i^{th}$ ( plank which has the color Si$S_i$ ) to a color P$P$ then following events happen:

• if 2≤i≤N$2\le i\le N$ and Si=Si−1$S_i=S_{i-1}$, then color of (i−1)th$(i-1{)}^{th}$ plank changes to P$P$.
• if 1≤i≤N−1$1\le i\le N-1$ and Si=Si+1$S_i=S_{i+1}$, then color of (i+1)th$(i+1{)}^{th}$ plank changes to P$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 : BBWWWB$BBWWWB$ If Ryan colors the fourth plank( whose color is W$W$ ) to color B$B$, then the finally the planks would be colored as following:

BBBBBB$BBBBBB$

Ryan can choose any one of the N$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$T$, number of testcases. Then the testcases follow.
• The first line of each test case consists of an integer N$N$ the number of planks
• Second line of each test case consists of a string S$S$ of size N$N$,where the i$i$ th character denotes the color of plank i$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≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• S$S$ consists only of characters B$B$ and W$W$
• The sum of N$N$ over all cases doesn't exceed 105${10}^5$.

Sample Input 1 

4
6
BBWWWB
5
WWBWB
2
BB
9
WWBBBBBWW

Sample Output 1 

1
2
0
1

Explanation

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

Test case 2: Ryan can paint the third plank to W$W$. After doing so the color string of planks become WWWWB$WWWWB$. Then he can again paint the third plank to the color B$B$. After doing so the string goes through following transitions:

• The color of third plank changes to B$B$. ( The string becomes WWBWB$WWBWB$ )
• The color of second and fourth plank changes to B$B$. ( The string becomes WBBBB$WBBBB$ )
• The color of first plank changes to B$B$. ( The string becomes BBBBB$BBBBB$ )

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$3$ to 7$7$ to W$W$, and all these planks will be colored to W$W$!

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {

// your code goes here

int t,n;

cin>>t;

while(t--){

    cin>>n;

    string s; cin>>s;int temp = 0;

    int answer =0;

    for(int i=0;i<n;i++){

        if(s[i] == 'W'){

            int j=i+1;

            while(j<n && s[j] == s[i]) j++;

            temp +=j;

        }

        else if(i>0 && s[i] != s[i-1]){

            answer++;

            int k = i + 1;

            while(k<n && s[k] == s[i]) k++;

            temp+=k;

        }

        else{

            int k = i + 1;

            while(k<n && s[k] == s[i]) k++;

            temp+=k;

        }

    }

    if(temp) cout<<answer<<endl;

    else cout<<0<<endl;

}

}