Xenny was a teacher and his class consisted of N boys and N girls. He took all his students to the playground and asked them to stand in a straight line. The boys and the girls formed a perfect line, but Xenny seemed unhappy. He wanted them to form an alternating sequence of boys and girls, i.e., he wanted that after a boy, there should be a girl in the line, and vice-versa.

In order to form an alternating sequence, a boy and a girl could swap their positions.

Given the original sequence in which the boys and girls were standing, find the minimum number of swaps required to form an alternating sequence.

Note: An alternating sequence can start either with a boy or a girl.

Input
First line of input consists of a natural number T - the number of testcases.
T testcases follow. For each testcase:

First line consists of a single integer N - the number of boys, and the number of girls.
Second line consists of a string of length 2N, representing the original sequence.
In this string, a boy is represented by uppercase character B and a girl by G.

Output
For each testcase, print the minimum number of swaps required to get an alternating sequence on a new line.

Constraints
1 ≤ T ≤ 5

1 ≤ N ≤ 10^6

SAMPLE INPUT
1
2
BBGG

SAMPLE OUTPUT
1

Explanation

The first boy from left  can swap his position with the first girl from right to get the sequence:

GBGB

This is an alternating sequence and it was obtained using 1 swap.
def func(typ,k,bg):
    count=0
    if typ==0:
        for i in range(len(k)):
            if k[i]!=bg[i]:
                count+=1
        return count/2
    if typ==1 or typ==2:
        b=[]
        g=[]
        for i in range(len(k)):
            if k[i]!=bg[i]:
                if k[i]=='B':
                    b.append(i)
                else:
                    g.append(i)
        for i in range(len(b)):
            count=count+1
        return count
for i in range(input()):
    typ=input()
    k=raw_input()
    b= k.count("B")
    g= k.count("G")
    bg=''
    gb=''
    for j in range(len(k)/2):
        bg=bg+'BG'
        gb=gb+'GB'
    if len(k)%2==1:
        bg=bg+'B'
        gb=gb+'G'
    
    if b==g:
        v1=func(1,k,bg)
        v2=func(1,k,gb)
        print min(v1,v2)
    elif b==g+1:
        v1=func(1,k,bg)
        print v1
    elif g==b+1:
        v2=func(1,k,gb)
        print v2
    else:
        print -1