You are given a string $s$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's.

String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even).

In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string.

What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010...


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$; $n$ is even) — the length of string $s$.

The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in$ {0, 1}). String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $10^5$.


-----Output-----

For each test case, print the minimum number of operations to make $s$ alternating.


-----Example-----
Input
3
2
10
4
0110
8
11101000

Output
0
1
2



-----Note-----

In the first test case, string 10 is already alternating.

In the second test case, we can, for example, reverse the last two elements of $s$ and get: 0110 $\rightarrow$ 0101.

In the third test case, we can, for example, make the following two operations:   11101000 $\rightarrow$ 10101100;  10101100 $\rightarrow$ 10101010.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    ans = 0
    for y in range(1, n):
        if s[y] == s[y-1]:
            ans += 1
    print((ans + ans % 2) // 2)
    


import sys
input=sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    s = input().strip()
    c = 0
    for i in range(n-1):
        if s[i] == s[i+1]:
            c += 1
    print((c+1)//2)

t = int(input())

for q in range(t):
    n = int(input())
    s = input()
    a, b = 0, 0
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            if s[i] == '0':
                a += 1
            else:
                b += 1
    print(max(a, b))


import collections
import math
from itertools import permutations as p

for t in range(int(input())):
    n=int(input())
    s=input()
    stack=[]
    for i in s:
        if i=='1':
            if stack and stack[-1]=='0':
                stack.pop()
        else:
            if stack and stack[-1]=='1':
                stack.pop()
        stack.append(i)
    print(len(stack)//2)

import sys

input = sys.stdin.readline


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)


def lcm(a, b):
    return (a * b) / gcd(a, b)

def main():
    for _ in range(int(input())):
        n=int(input())
        # a=list(map(int, input().split()))
        s=input()
        c=0
        for i in range(1,len(s)):
            if s[i]==s[i-1]:
                c+=1
        print(c//2+c%2)

    return

def __starting_point():
    main()


__starting_point()

for _ in range(int(input())):
    n = int(input())
    *s, = list(map(int, input()))
    cnt = [0, 0]
    for i in range(len(s)):
        if i > 0 and s[i] == s[i - 1]:
            cnt[s[i]] += 1
    print(max(cnt))




import sys

def main():
    n = int(sys.stdin.readline().strip())
    #n, m = map(int, sys.stdin.readline().split())
    #q = list(map(int, sys.stdin.readline().split()))
    s = sys.stdin.readline().strip()
    res = 0
    i = 0
    while i < n:
        while i < n and s[i] != "1":
            i += 1
        if i >= n:
            break
        while i < n and s[i] == "1":
            i += 1
            res += 1
            #print(i, res)
        i += 1
        res -= 1
        #print(" ", i, res)
    i = 0
    ans = 0
    while i < n:
        while i < n and s[i] != "0":
            i += 1
        if i >= n:
            break
        while i < n and s[i] == "0":
            i += 1
            ans += 1
            #print(i, res)
        i += 1
        ans -= 1
        #print(" ", i, res)
    print(max(ans, res))
    
   
        
        
            
        
                
            
            
        
            
    
    
    
    
    
    
            
                
        
    
            
        

            
        
    
                
    
    
    
            
    
        
    

for i in range(int(sys.stdin.readline().strip())):
    main()

ans = []
for _ in range(int(input())):
    n = int(input())
    u = list(map(int, list(input())))
    cnt1 = cnt0 = 0
    for i in range(1, n):
        if u[i] == u[i - 1]:
            if u[i] == 0:
                cnt0 += 1
            else:
                cnt1 += 1
    ans.append(max(cnt1, cnt0))
print(*ans, sep='\n')


def solve(n):
    s=input()
    ans=0
    flag=0
    for i in range(n-1):
        if s[i]==s[i+1]:
            if flag==1:
                ans+=1
                flag=0
            else:
                flag=1
    if flag:
        ans+=1
    return ans

for _ in range(int(input())):
    print(solve(int(input())))



for _ in range(int(input())):
    n = int(input())
    s = input()
    blocks = [[s[0], 1]]
    for i in range(1, n):
        if s[i] == blocks[-1][0]:
            blocks[-1][1] += 1
        else:
            blocks += [[s[i], 1]]
    one = 0
    zero = 0
    for i in range(len(blocks)):
        if blocks[i][0] == '0':
            zero += blocks[i][1] - 1
        else:
            one += blocks[i][1] - 1
    print(max(one, zero))

for _ in range(int(input())):
    n = int(input())
    s = input()
    l = list(s)
    c0 = 0
    c1 = 0
    for i in range(n-1):
        if(l[i] == l[i+1]):
            if(l[i] == '0'):
                c0 += 1
            else:
                c1 += 1

    print(max(c0, c1))


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    S = 0
    for j in range(1,len(s)):
        if s[j-1]=='1' and s[j]=='1':
            S+=1
    if s[0]=='1' and s[-1]=='1' and len(s)>2:
        S+=1
    print(S)


import sys
input=sys.stdin.readline

T=int(input())
for _ in range(T):
    n=int(input())
    s=input()
    ans1=0
    ans2=0
    i=0
    while(i<n):
        c=1
        while (s[i]==s[i-1]):
            c=c+1
            i=i+1
            
        if (s[i-1]=='1'):
            ans2=ans2+c-1
        else:
            ans1=ans1+c-1
        i=i+1
    print(max(ans1,ans2))
            
            


t=int(input())
for i in range(t):
    n=int(input())
    s=input().strip()
    o=0
    z=0
    for j in range(1,n):
        if s[j]==s[j-1]:
            if s[j]=='1':
                o=o+1
            else:
                z=z+1
    print(max(z,o))

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def RLE(data):
    from itertools import groupby

    return [(x, len(list(grp))) for x, grp in groupby(data)]


def check(S, T):
    A = [0] * N
    for i in range(N):
        if S[i] != T[i]:
            A[i] = 1
    
    rle = RLE(A)
    cnt = 0
    for x, _ in rle:
        if x:
            cnt += 1
    return cnt

for _ in range(INT()):
    N = INT()
    S = input()

    T1 = '01' * (N//2)
    T2 = '10' * (N//2)

    ans = min(check(S, T1), check(S, T2))
    print(ans)


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    S=input().strip()

    A=0
    for i in range(1,n):
        if S[i]==S[i-1]:
            A+=1

    print((A+1)//2)


for irjfr in range(int(input())):
    input()
    s = input()
    res = int(s[0] == s[-1] == '1')
    for i in range(len(s) - 1):
        res += int(s[i] == s[i + 1] == '1')
    print(res)

for _ in range(int(input())):
    n = int(input())
    s = input()
    ans1 = 0
    ans2 = 0
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            if s[i] == '0':
                ans1 += 1
            else:
                ans2 += 1
    print(max(ans1, ans2))


import math
for  _ in range(int(input())):
    n = int(input())
    s = input()
    r = 0
    for i in range(1,n):
        if s[i-1] != s[i]:
            continue
        else:
            r+=1
    print(math.ceil(r/2))