xenny-and-classroom-circuits

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.

Source: hackerearth | Difficulty: EASY
Tags: Ad-hoc


Solutions:
for _ in range(eval(input())):
	n=eval(input())
	b=input()
	s1=['G']*(2*n)
	s2=['G']*(2*n)
	j=count1=count2=0
	for i in range(1,2*n,2):
		s1[i]='B'
		s2[j]='B'
		j=j+2
	for i in range(2*n):
		if b[i]!=s1[i]:
			count1+=1
		if b[i]!=s2[i]:
			count2+=1
	print(min(count1/2,count2/2))


import sys

for __ in range(eval(input())) :
	n = eval(input())
	s = list(input())
	seq0 , seq1 = "BG"*n , "GB"*n
	a0 , a1 = 0 , 0
	k = [i for i in s]
	i = 0
	while i < 2*n :
		if s[i] != seq0[i] :
			j = i+1
			while j < 2*n and seq0[j] == s[j] :
				j += 1
			if j < 2*n :
				s[i] , s[j] = seq0[i] , seq0[j]
				a0 += 1
			else :
				break
		i += 1
	s = [i for i in k]
	i = 0
	while i < 2*n :
		j = 1
		if s[i] != seq1[i] :
			j = i+1
			while j<2*n and seq1[j] == s[j] :
				j += 1
			if j < 2*n :
				s[i] , s[j] = seq1[i] , seq1[j]
				a1 += 1
			else :
				break
		i  += 1
	print(min(a1,a0))


for _ in range(eval(input())):
	n=eval(input())
	s=input()
	b=g=0
	for i in range(n):
		if s[2*i]!='B':
			b+=1
		if s[2*i]!='G':
			g+=1
	print(min(b,g))


#
import fileinput
import numpy as np
import __future__


new=[]
T=[]

i=0
testes=1
for line in fileinput.input():
	conta=0
	if i > 2*testes:
		break
	
	elif i == 0:
		testes=int(line)

	elif i%2== 1:
		n=int(line)

	else:
		ini=line[0]
		fin='B'
		if line[0]=='B':
			fin='G'
		errado = fin
		num=0
		for c in line:
			if c == errado:
				conta+=1
			if errado == ini:
				errado = fin
			else:
				errado = ini
			num+=1
			if num > 2*n:
				break
		if conta > n:
			print((int(n-conta/2)))
		else:
			print((int(conta/2)))
	i+=1
		
	



t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	B = 0
	G = 0
	for j in range(0, 2*n, 2):
		if s[j] == 'B':
			B += 1
		else:
			G += 1
	print(min(B, G))


for _ in range(int(input())):
	n=int(input())
	s=input()
	s1='BG'*n
	s2='GB'*n
	count1=0
	count2=0
	for i in range(2*n):
		if s[i]!=s1[i]:
			count1+=1
		if s[i]!=s2[i]:
			count2+=1

	print(min(count1,count2)/2)
			
		


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(eval(input())):
	typ=eval(input())
	k=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)


def swaps(placing, number):
	pattern1 = 'BG' * (number)
	pattern2 = 'GB' * (number)
	count1 = 0
	count2 = 0
	for i in range(len(placing)):
		if placing[i] != pattern1[i]:
			count1 += 1
		if placing[i] != pattern2[i]:
			count2 += 1
	return min(count1 / 2, count2 / 2)

if __name__ == '__main__':
	answer = []
	T = eval(input())
	for i in range(T):
		number = eval(input())
		placing = input()
		answer.append(swaps(placing, number))
	for i in answer:
		print(i)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())

for i in range(t):
	n = int(input())
	st = input()
	s = st[0]
	count = 0
	for i in range(len(st)):
		if ((i&1) == 0 and s != st[i]) or ((i&1) == 1 and s == st[i]):
			count += 1
			
	print(min (count>>1, n-(count>>1)))
	


test_cases = int(input())
if test_cases > 5 or test_cases < 1:
	print(0)
else:
	for each_test_case in range(0, test_cases):
		N = int(input())
		if N < 1 or N > pow(10, 6):
			print(0)
			continue
		seq = input()
		if len(seq) != 2 * N:
			print(0)
			continue
		total_B = 0
		total_G = 0
		index = 0
		while index < len(seq):
			if seq[index] == 'B':
				total_B += 1
			else:
				total_G += 1
			index += 2
		print((min(total_B, total_G)))


T = int(eval(input()));
for i in range(0,T):
	N = int(eval(input()));
	line = str(input());
	pos = 0;
	out_of_pos_count = 0;
	for c in line:
		if pos % 2 == 0:
			if c != 'B':
				out_of_pos_count+=1;
		pos+=1;

	if out_of_pos_count > int(N/2):
		out_of_pos_count = N - out_of_pos_count;
	print((int(out_of_pos_count)));



def process(A,n):
	pairs = 0
	bg_reversed = 0
	gb_reversed = 0
	for e in A:
		if e == ('B','G'):
			bg_reversed += 1
		elif e == ('G','B'):
			gb_reversed += 1
		else:
			pairs += 1
	return (pairs/2) + min(bg_reversed, gb_reversed)

for _ in range(eval(input())):
	n = eval(input())
	s = input()
	A = list(zip(s[::2], s[1::2]))
	print(process(A, n))



T = int(input())
for i in range(T):
	N = int(input())
	line = str(input())
	bg_boxes = 0
	gb_boxes = 0
	for j in range(N):
		if(line[2*j: 2*j+2] == "BG"):
			bg_boxes += 1
		elif(line[2*j: 2*j+2] == "GB"):
			gb_boxes += 1
		
	
	result = min(bg_boxes, gb_boxes) + (N-bg_boxes - gb_boxes)/2
	print(result)


def swaps(arng,reqarng):
	count = 0 
	for i in range(len(arng)):
		if arng[i]!=reqarng[i]:
			count = count + 1
	return count/2


t = int(eval(input()))
for i in range(t):
	n = int(eval(input()))
	arng = input()
	for j in range(2*n):
		if j==0:
			reqarng = "B"
		else:
			if j%2==0:
				reqarng = reqarng + "B"
			else:
				reqarng = reqarng + "G"
	s1 = swaps(arng,reqarng)
	s2 = swaps(arng,reqarng[::-1])
	if s1>s2:
		print(s2)
	else:
		print(s1)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(eval(input()))
for i in range(n):
	m=int(eval(input()))
	st=input()
	count_b=0
	count_a=0
	i=-2
	while(i+2<len(st)):
		if(st[i+2]=="B"):
			count_b+=1
		else:
			count_a+=1
		i+=2
	#print(count_a,count_b)
	if(count_b==count_a):
		print(count_b)
	elif(count_b==0 or count_a==0):
		print((0))
	else:
		if(count_b>count_a):
			print(count_a)
		else:
			print(count_b)
	



for i in range(int(input())):
	n = int(input())
	s = input()
	c1 = 0
	c2 = 0
	for j in range(0,(2*n)-1,2):
		if s[j]=='B':
			c2+=1
		else:
			c1+=1
		if s[j+1]=='B':
			c1+=1
		else:
			c2+=1
	if c1<c2:
		print(c1/2)
	else:
		print(c2/2)


import sys

for __ in range(eval(input())) :
	n = eval(input())
	s = list(input())
	seq0 , seq1 = "BG"*n , "GB"*n
	a0 , a1 = 0 , 0
	k = [i for i in s]
	i = 0
	while i < 2*n :
		j = 1
		if s[i] != seq0[i] :
			j = i+1
			while j < 2*n and seq0[j] == s[j] :
				j += 1
			if j < 2*n :
				s[i] , s[j] = seq0[i] , seq0[j]
				a0 += 1
			else :
				break
		i += 1
	s = [i for i in k]
	i = 0
	while i < 2*n :
		j = 1
		if s[i] != seq1[i] :
			j = i+1
			while j<2*n and seq1[j] == s[j] :
				j += 1
			if j < 2*n :
				s[i] , s[j] = seq1[i] , seq1[j]
				a1 += 1
			else :
				break
		i  += 1
	print(min(a1,a0))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = list(s)
	count1 = 0
	
	for j in range(n):
		k=2*j
		if (s[0]==s[k]):
			count1+=1
	count2=n-count1
	ans = min(count1,count2)
		
	print(ans)
	



t=int(input())
for i in range(t):
	num=int(input())
	seq=input()
	if(seq[0]=='G'):
		final="GB"*num
	else:
		final="BG"*num
	swapg=0
	swapb=0
	for j in range(num*2):
		if(seq[j]!=final[j] and seq[j]==seq[0]):
			swapg+=1
			
	if(seq[0]=='G'):
		final="BG"*num
	else:
		final="GB"*num
	for j in range(num*2):
		if(seq[j]!=final[j] and seq[j]==seq[0]):
			swapb+=1
	print((min(swapg,swapb)))


t=int(input())
for i in range(t):
	num=int(input())
	seq=input()
	if(seq[0]=='G'):
		final="GB"*num
	else:
		final="BG"*num
	swapg=0
	swapb=0
	for j in range(num*2):
		if(seq[j]!=final[j] and seq[j]==seq[1]):
			swapg+=1
			
	if(seq[0]=='G'):
		final="BG"*num
	else:
		final="GB"*num
	for j in range(num*2):
		if(seq[j]!=final[j] and seq[j]==seq[1]):
			swapb+=1
	print((min(swapg,swapb)))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
test = int(input())

boys = [0]*test
text = [None]*test 

for i in range(test):
	boys[i] = int(input())
	text[i] = input()



for i in range(test):
	
	misplacedGinBG = misplacedBinBG = misplacedBinGB = misplacedGinGB = 0
	for index, c in enumerate(text[i]):
		if ((index+1)%2==1):
			if (c== 'G'):
				misplacedGinBG = misplacedGinBG+1
			else:
				misplacedBinGB = misplacedBinGB+1
				
		else:
			if (c == 'B'):
				misplacedBinBG = misplacedBinBG+1
			else:
				misplacedGinGB = misplacedGinGB+1
			
	print(min(misplacedGinBG, misplacedBinBG, misplacedBinGB, misplacedGinGB))


'''
	Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t= int(input())
while(t):
	n=eval(input())
	odr = input()
	arr=[]
	arr1=[]
	arr2=[]
	count1=0
	count2=0
	le = len(odr)
	for i in range(le):
	    if (odr[i]=="G"):
	        arr.append(1)
	    else:
	        arr.append(-1)
	for i in range(le):
	    if i%2==0:
	        arr1.append(1)
	        arr2.append(-1)
	    else:
	        arr1.append(-1)
	        arr2.append(1)
	
	for i in range(le):
	    if(arr[i]+arr1[i]==0):
	        count1=count1+1
	    if(arr[i]+arr2[i]==0):
	        count2=count2+1
	print(min(count1,count2)/2)
	t=t-1
								


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input());
for i in range(0,t):
	n=int(input());
	str1=input();
	list1=[];
	list2=[];
	list3=[];
	list4=[];
	for j in range(0,(2*n),2):
		if(str1[j]!="B"):
			list1.append(j);
	for k in range(1,(2*n),2):
		if(str1[k]!="G"):
			list2.append(k);
	count1=len(list1);
	for j in range(1,(2*n),2):
		if(str1[j]!="B"):
			list3.append(j);
	for k in range(0,(2*n),2):
		if(str1[k]!="G"):
			list4.append(k);
	count2=len(list3);
	if(count1<count2):
		print(count1);
	else:
		print(count2);


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=eval(input())
while(t):
	n=eval(input())
	s=input()
	l=len(s)
	lst1=list()
	lst2=list()
	ans=0
	c1=0
	c2=0
	for x in range(0,l,2):
		if(s[x]==s[x+1]):
			lst1.append(s[x])
			lst1.append(s[x+1])
		else:
			lst2.append(s[x])
			lst2.append(s[x+1])
	#print lst1,' ',lst2
	if lst1:
		ans=lst1.count('B')
	if lst2:
		l2=len(lst2)
		for x in range(0,l2,2):
			if(lst2[x]=='B' and lst2[x+1]=='G'):
				c1=c1+1
			elif(lst2[x]=='G' and lst2[x+1]=='B'):
				c2=c2+1
#print c1,' ',c2
	if(c1>c2):
		ans = (ans/2) + c2
	else:
		ans = (ans/2) + c1
	print(ans)
	t=t-1



q=eval(input())
for _ in range(q):
	x=eval(input())
	t=input()
	a,b,n,m=0,0,0,0
	for y in range(2*x):
		if y%2==0:
			if t[y]=='B':
				a+=1
			else:
				b+=1
		else:
			if t[y]=='B':
				n+=1
			else:
				m+=1
	print(min(a,b,n,m))