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$!

Difficulty: MEDIUM
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	x = int(input())
	str1 = input()
	count = 0
	dic = {'B': 0, 'W': 0}
	for i in range(1, len(str1)):
		if str1[i] == str1[i - 1]:
			pass
		else:
			dic[str1[i - 1]] += 1
	dic[str1[len(str1) - 1]] += 1
	print(min(dic.values()))


t = int(input())
for z in range(t):
	n = int(input())
	s = input()
	w = 0
	b = 0
	i = 0
	while i < n:
		temp = s[i]
		while True:
			if i < n - 1 and temp == s[i + 1]:
				i = i + 1
			else:
				if temp == 'B':
					b = b + 1
				elif temp == 'W':
					w = w + 1
				i = i + 1
				break
	print(min(b, w))


tt = 100
s = tt - 10
t = int(input())
for i in range(t):
	n = int(input())
	str = input()
	a = 0
	a2 = 0
	a3 = str[0]
	if a3 == 'W':
		a = a + 1
	else:
		a2 = a2 + 1
	for j in range(n):
		if a3 == str[j]:
			continue
		elif str[j] == 'B':
			a2 = a2 + 1
		else:
			a = a + 1
		a3 = str[j]
	print(min(a, a2))


for t in range(int(input())):
	n = int(input())
	s = input()
	s = list(s)
	s1 = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			s1 += 1
	print((s1 + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	for i in range(n - 1):
		if s[i] == 'W' and s[i + 1] == 'B' or (s[i] == 'B' and s[i + 1] == 'W'):
			cnt += 1
	print(cnt // 2 + cnt % 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	s1 = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			s1 += 1
	if s1 <= 1:
		print(s1)
	else:
		print((s1 + 1) // 2)


t = int(input())
for i in range(t):
	le = int(input())
	str1 = input()
	str1 += ' '
	lis = list(set(list(str1)))
	if len(lis) == 1:
		print(0)
	else:
		cntw = 0
		cntb = 0
		outlw = []
		outlb = []
		for i in range(len(str1)):
			if i == len(str1) - 1:
				if str1[i - 1] == 'W':
					outlw.append(cntw)
				else:
					outlb.append(cntb)
			elif i != len(str1) - 1 and str1[i] == 'W':
				cntw += 1
				outlb.append(cntb)
				cntb = 0
			elif i != len(str1) - 1 and str1[i] == 'B':
				outlw.append(cntw)
				cntw = 0
				cntb += 1
		cntw0 = outlw.count(0)
		cntb0 = outlb.count(0)
		print(min(len(outlw) - cntw0, len(outlb) - cntb0))


for i in range(int(input())):
	no = int(input())
	st = input()
	b = 0
	w = 0
	pre = st[0]
	for i in st[1:]:
		if pre == i:
			continue
		else:
			if pre == 'B':
				b += 1
			else:
				w += 1
			pre = i
	if pre == 'B':
		b += 1
	else:
		w += 1
	print(min(b, w))


import re
for i in range(int(input())):
	n = int(input())
	str1 = input()
	list1 = re.findall('W+', str1)
	list2 = re.findall('B+', str1)
	print(min(len(list1), len(list2)))


T = int(input())
for i in range(T):
	bStreak = 0
	wStreak = 0
	N = int(input())
	S = input()
	i = 0
	while i < len(S):
		if S[i] == 'B':
			bStreak += 1
			i += 1
			while i < len(S) and S[i] == 'B':
				i += 1
		else:
			wStreak += 1
			i += 1
			while i < len(S) and S[i] == 'W':
				i += 1
	print(min(bStreak, wStreak))


for i in range(int(input())):
	n = int(input())
	a = input()
	(x, y) = (0, 0)
	if a[0] == 'W':
		x += 1
	else:
		y += 1
	b = a[0]
	for j in range(n):
		if b == a[j]:
			continue
		elif a[j] == 'B':
			y += 1
		else:
			x += 1
		b = a[j]
	print(min(x, y))


for i in range(int(input())):
	n = int(input())
	s = input()
	if len(set(s)) == 1:
		print(0)
	else:
		i = 0
		l = s[0]
		while i < n - 1:
			if s[i] != s[i + 1]:
				l += s[i + 1]
			i += 1
		print(min(l.count('W'), l.count('B')))


t = int(input())
for _ in range(0, t):
	n = int(input())
	s = input()
	lst = list()
	if s[0] == 'B':
		lst.append(0)
	else:
		lst.append(1)
	for i in s[1:]:
		if i == 'B' and lst[-1] != 0:
			lst.append(0)
			continue
		if i == 'W' and lst[-1] != 1:
			lst.append(1)
			continue
	ans = min(lst.count(0), lst.count(1))
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	W = S.count('BW')
	B = S.count('WB')
	if S[0] == 'B':
		B += 1
	else:
		W += 1
	ans.append(min(W, B))
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	c = {'B': 0, 'W': 0}
	c[S[0]] = 1
	for i in range(1, N):
		if S[i - 1] == S[i]:
			continue
		c[S[i]] += 1
	an = min(c['B'], c['W'])
	ans.append(an)
outplt(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l1 = s.split('B')
	l2 = s.split('W')
	print(min(len(l1) - l1.count(''), len(l2) - l2.count('')))


for i in range(int(input())):
	n = int(input())
	s = input()
	(x, y) = (0, 0)
	if s[0] == 'W':
		x += 1
	else:
		y += 1
	p = s[0]
	for j in range(n):
		if p == s[j]:
			continue
		elif s[j] == 'B':
			y += 1
		else:
			x += 1
		p = s[j]
	print(min(x, y))


for _ in range(int(input())):
	n = input()
	fence = input()
	prev = fence[0]
	cnt = 0
	for i in fence:
		if i != prev:
			cnt += 1
			prev = i
	print((cnt + 1) // 2)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	char = string[0]
	count = 0
	for j in range(1, length):
		if string[j] != char:
			count += 1
			char = string[j]
	count += 1
	print(count // 2)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	B_changes = 0
	W_changes = 0
	temp = 1
	for j in range(1, length):
		if string[j] != string[j - 1]:
			if string[j - 1] == 'B':
				B_changes += 1
			else:
				W_changes += 1
			temp = 1
		else:
			temp += 1
	if string[-1] == 'B':
		B_changes += 1
	else:
		W_changes += 1
	print(min(B_changes, W_changes))


for i in range(int(input())):
	n = int(input())
	s = input()
	check = s[0]
	count = 0
	for i in s:
		if i != check:
			count += 1
			check = i
	print((count + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	pre = s1[0]
	count = 0
	for i in s1:
		if i != pre:
			count += 1
			pre = i
	print((count + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	color = input()
	streakW = streakB = 0
	prev = ''
	for i in color:
		if i != prev:
			if i == 'B':
				prev = 'B'
				streakB += 1
			else:
				prev = 'W'
				streakW += 1
	print(min(streakW, streakB))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = s[0]
	d = {'B': 0, 'W': 0}
	d[x] = 1
	for j in range(len(s) - 1):
		if s[j] == 'B' and s[j + 1] == 'W':
			d['W'] = d['W'] + 1
			continue
		elif s[j] == 'W' and s[j + 1] == 'B':
			d['B'] = d['B'] + 1
			continue
	if d['B'] <= d['W']:
		print(d['B'])
	else:
		print(d['W'])


t = int(input())
from itertools import groupby
for _ in range(t):
	n = int(input())
	s = input()
	cnt_b = 0
	cnt_w = 0
	for (key, val) in groupby(s):
		if key == 'B':
			cnt_b += 1
		else:
			cnt_w += 1
	print(min(cnt_w, cnt_b))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	w = b = 0
	if s[0] == 'B':
		b += 1
	else:
		w += 1
	for i in range(1, n):
		if s[i] != s[i - 1] and s[i] == 'B':
			b += 1
		elif s[i] != s[i - 1] and s[i] == 'W':
			w += 1
	print(min(b, w))


for _ in range(int(input())):
	n = int(input())
	l = input()
	cb = 0
	cw = 0
	curr = l[0]
	for i in range(n):
		if curr == l[i]:
			continue
		elif curr == 'B':
			cb = cb + 1
		else:
			cw = cw + 1
		curr = l[i]
	if curr == 'B':
		cb = cb + 1
	else:
		cw = cw + 1
	print(min(cw, cb))


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = s[0]
	w = 0
	b = 0
	for i in s:
		if i != x:
			if x == 'B':
				b += 1
			else:
				w += 1
			x = i
	if x == 'B':
		b += 1
	else:
		w += 1
	print(min(b, w))


for t in range(int(input())):
	n = int(input())
	s = input()
	res = 0
	(c_b, c_w) = (0, 0)
	for i in range(n - 1):
		if s[i] != s[i + 1] and s[i] == 'W':
			c_w += 1
		elif s[i] != s[i + 1] and s[i] == 'B':
			c_b += 1
	if s[-1] == 'B':
		c_b += 1
	else:
		c_w += 1
	print(min(c_b, c_w))


T = int(input())
for i in range(T):
	n = int(input())
	string = input()
	if string[0] == 'W' and string[-1] == 'W':
		val = 'W'
	else:
		val = 'B'
	countB = 0
	m = 0
	n = n - 1
	if not ('B' in string and 'W' in string):
		print(0)
		continue
	while m <= n:
		change = False
		while m <= n:
			if string[m] == val:
				m += 1
			else:
				change = True
				break
		while m <= n:
			if string[n] == val:
				n -= 1
			else:
				change = True
				break
		if change == True:
			if val == 'B':
				val = 'W'
			else:
				val = 'B'
			countB += 1
		else:
			break
	print(countB)


import math
tcase = int(input().rstrip())
output = []
for i in range(tcase):
	slen = int(input().rstrip())
	string = input().rstrip()
	code = string[0]
	for j in range(1, slen):
		if string[j] != code[len(code) - 1]:
			code = code + string[j]
	if len(code) == 1:
		output.append(0)
	elif len(code) >= 2:
		output.append(math.floor(len(code) / 2))
for i in output:
	print(i)


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	p = 0
	q = 0
	for i in range(n - 1):
		if s[0] == 'W':
			if s[i] == 'W' and s[i + 1] == 'B':
				p += 1
				q += 1
			else:
				p += 1
		elif s[i] == 'B' and s[i + 1] == 'W':
			p += 1
			q += 1
		else:
			q += 1
	print(min(p, q))


T = int(input())
for _ in range(T):
	n = int(input())
	s = str(input())
	cnt_black = 0
	cnt_white = 0
	curr = s[0]
	for i in range(0, n):
		if s[i] == curr:
			continue
		else:
			if curr == 'B':
				cnt_black += 1
			else:
				cnt_white += 1
			curr = s[i]
	if curr == 'B':
		cnt_black += 1
	else:
		cnt_white += 1
	print(min(cnt_white, cnt_black))


def devs(n, l):
	cb = 0
	cw = 0
	curr = l[0]
	for i in range(n):
		if curr == l[i]:
			continue
		elif curr == 'B':
			cb = cb + 1
		else:
			cw = cw + 1
		curr = l[i]
	if curr == 'B':
		cb = cb + 1
	else:
		cw = cw + 1
	print(min(cw, cb))
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(str, input().strip()))[:n]
	devs(n, l)


def solution(planks):
	switches = 1
	for i in range(1, len(planks)):
		if planks[i] != planks[i - 1]:
			switches += 1
	return switches // 2
for i in range(0, int(input())):
	_ = input()
	letters = input()
	print(solution(letters))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	b = w = 0
	cur = s[0]
	for i in range(n):
		if cur == s[i]:
			continue
		else:
			if cur == 'B':
				b += 1
			else:
				w += 1
			cur = s[i]
	if cur == 'B':
		b += 1
	else:
		w += 1
	print(min(b, w))


n = int(input())
while n > 0:
	n -= 1
	m = int(input())
	s = input()
	if 'B' not in s or 'W' not in s:
		print(0)
	else:
		t = s.count('WB')
		t1 = s.count('BW')
		if t == t1:
			print(t1)
		else:
			print(max(t, t1))


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = s[0]
	for i in range(1, n):
		if l[-1] != s[i]:
			l += s[i]
	print(len(l) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(b, w) = (0, 0)
	if s[0] == 'W':
		w += 1
	else:
		b += 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1] and s[i] == 'W':
			w += 1
		elif s[i] != s[i - 1] and s[i] == 'B':
			b += 1
	if len(set(s)) == 1:
		print(0)
	else:
		print(min(w, b))


n = int(input())
for _ in range(n):
	a = int(input())
	lis = input()
	c = 1
	for i in range(a - 1):
		if lis[i] != lis[i + 1]:
			c += 1
	print(c // 2)


for _ in range(int(input())):
	n = int(input())
	count = 1
	ip = list(map(str, input()))
	for i in range(n - 1):
		if ip[i] != ip[i + 1]:
			count = count + 1
	print(count // 2)


for _ in range(int(input())):
	n = int(input())
	li = input()
	countw = 0
	countb = 0
	i = 0
	while i < n:
		if li[i] == 'W':
			while i + 1 < n and li[i] == li[i + 1]:
				i += 1
			countw += 1
		elif li[i] == 'B':
			while i + 1 < n and li[i] == li[i + 1]:
				i += 1
			countb += 1
		i += 1
	print(min(countb, countw))


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s[0]
	ans = 1
	for i in s:
		if i != a:
			a = i
			ans += 1
	print(ans // 2)


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


t = int(input())
for test in range(t):
	n = int(input())
	s = input()
	lks = s[0]
	for i in range(1, n):
		if lks[-1] != s[i]:
			lks += s[i]
	print(len(lks) // 2)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
for _ in range(inp()):
	n = inp()
	str = input()
	count = 0
	for i in range(n):
		if str[i - 1] != str[i]:
			count += 0.5
	print(floor(count))


for gagroz in range(int(input())):
	n = int(input())
	x = input()
	(b, w) = (0, 0)
	if x[0] == 'W':
		w += 1
	else:
		b += 1
	for i in range(1, n):
		if x[i - 1] != x[i]:
			if x[i] == 'W':
				w += 1
			else:
				b += 1
	print(min(b, w))


for i in range(int(input())):
	n = int(input())
	a = input()
	x = 0
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			x += 1
	if x % 2 == 0:
		print(x // 2)
	else:
		print(x // 2 + 1)


for _ in range(int(input())):
	n = input()
	data = input()
	swaps = 0
	current = data[0]
	for d in data[1:]:
		if d != current:
			swaps += 1
		current = d
	print((swaps + 1) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	k = s[0]
	(b, w) = (0, 0)
	for i in range(1, len(s)):
		if s[i] == k:
			continue
		else:
			if k == 'B':
				b += 1
			else:
				w += 1
			k = s[i]
	if k == 'B':
		b += 1
	else:
		w += 1
	print(min(w, b))


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


try:
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		d = dict()
		d['B'] = 0
		d['W'] = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				d[s[i - 1]] += 1
		d[s[n - 1]] += 1
		print(min(d['W'], d['B']))
except:
	pass


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	bh = 0
	bsep = 0
	bactive = False
	wh = 0
	wsep = 0
	wactive = False
	for j in range(0, n):
		if s[j] == 'W':
			if bactive == False and wactive == False:
				wactive = True
				wsep += 1
			elif bactive == True:
				bactive = False
				wactive = True
				wsep += 1
		elif s[j] == 'B':
			if bactive == False and wactive == False:
				bactive = True
				bsep += 1
			elif wactive == True:
				wactive = False
				bactive = True
				bsep += 1
	if bsep < wsep:
		print(bsep)
	else:
		print(wsep)


t = int(input())
for t in range(t):
	count_b = count_w = 0
	n = int(input())
	s = input()
	if s[0] == 'B':
		count_b = count_b + 1
	else:
		count_w = count_w + 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			if s[i] == 'B':
				count_b = count_b + 1
			else:
				count_w = count_w + 1
	if count_w < count_b:
		print(count_w)
	else:
		print(count_b)


for _ in range(int(input())):
	n = int(input())
	a = input()
	b = 0
	w = 0
	if a[0] == 'B':
		b += 1
	elif a[0] == 'W':
		w += 1
	for i in range(1, n):
		if a[i] != a[i - 1] and a[i] == 'B':
			b += 1
		elif a[i] != a[i - 1] and a[i] == 'W':
			w += 1
	print(min(b, w))


def orican(N, s):
	o = 1
	for i in range(1, N):
		if s[i - 1] != s[i]:
			o += 1
	return o // 2
t = int(input())
for _ in range(t):
	N = int(input())
	s = input()
	result = orican(N, s)
	print(result)


t = int(input())
for z in range(t):
	n = int(input())
	a = list(input())
	if a[len(a) - 1] == '\r':
		a.pop()
	c1 = 0
	c2 = 0
	x = a[0]
	for i in range(1, len(a)):
		if a[i] != x:
			if x == 'B':
				c1 += 1
			else:
				c2 += 1
			x = a[i]
	if x == 'B':
		c1 += 1
	else:
		c2 += 1
	print(min(c1, c2))


import itertools
for _ in range(int(input())):
	n = int(input())
	a = input()
	x = itertools.groupby(a)
	count = 0
	count2 = 0
	for (k, g) in x:
		if k == 'W':
			count += 1
		if k == 'B':
			count2 += 1
	print(min(count, count2))