This is the easy version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $s$ of length $n$, consisting only of zeros and ones, $n$ is even.

Now Tokitsukaze divides $s$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $s$ is considered good if the lengths of all subsegments are even.

For example, if $s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $2$, $2$, $4$ respectively, which are all even numbers, so "11001111" is good. Another example, if $s$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $3$, $2$, $2$, $3$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $s$ good by changing the values of some positions in $s$. Specifically, she can perform the operation any number of times: change the value of $s_i$ to '0' or '1'($1 \leq i \leq n$). Can you tell her the minimum number of operations to make $s$ good?


-----Input-----

The first contains a single positive integer $t$ ($1 \leq t \leq 10000$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of $s$, it is guaranteed that $n$ is even.

The second line contains a binary string $s$ of length $n$, consisting only of zeros and ones.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single line with one integer — the minimum number of operations to make $s$ good.


-----Examples-----

Input
5
10
1110011000
8
11001111
2
00
2
11
6
100110
Output
3
0
0
0
3


-----Note-----

In the first test case, one of the ways to make $s$ good is the following.

Change $s_3$, $s_6$ and $s_7$ to '0', after that $s$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $2$ and $8$ respectively. There are other ways to operate $3$ times to make $s$ good, such as "1111110000", "1100001100", "1111001100".

In the second, third and fourth test cases, $s$ is good initially, so no operation is required.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
from collections import defaultdict
import math as m
import sys
input = sys.stdin.readline

def cin2int():
	temp = input().split()
	return (int(temp[0]), int(temp[1]))

def cin3int():
	temp = input().split()
	return (int(temp[0]), int(temp[1]), int(temp[2]))

def cinarr():
	temp = input().split()
	return [int(x) for x in temp]

def solve():
	n = int(input())
	a = input()
	res = 0
	for i in range(1, n, 2):
		if a[i - 1] != a[i]:
			res += 1
	return res
for case in range(int(input())):
	print(solve())


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	res1 = 0
	for i in range(0, n - 1, 2):
		if s[i] != s[i + 1]:
			res1 += 1
	print(res1)


t = int(input())
out = ''
for j in range(t):
	n = int(input())
	s = input()
	ans = 0
	for i in range(0, len(s), 2):
		if s[i] != s[i + 1]:
			ans += 1
	out += str(ans) + '\n'
print(out)


for s in [*open(0)][2::2]:
	ch = s.__len__()
	count = 0
	for i in range(0, ch - 2, 2):
		if s[i] == s[i + 1]:
			pass
		else:
			count += 1
	print(count)


def solve() -> int:
	n = int(input())
	string = input()
	result = 0
	for index in range(0, n - 1, 2):
		if string[index] != string[index + 1]:
			result += 1
	return result
results = []
for _ in range(int(input())):
	results.append(str(solve()))
print('\n'.join(results))


n = int(input())
answer = []
for i in range(n):
	length = int(input())
	bstr = input()
	counter = 0
	for elem in range(0, length, 2):
		if bstr[elem] != bstr[elem + 1]:
			counter += 1
	answer.append(counter)
for ans in answer:
	print(ans)


t = int(input())
v = []
for i in range(t):
	v.append([int(input()), input()])
for i in v:
	ans = 0
	for j in range(0, i[0], 2):
		if i[1][j] != i[1][j + 1]:
			ans += 1
	print(ans)


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	string = input()
	ans = 0
	for i in range(0, len(string), 2):
		if string[i] != string[i + 1]:
			ans += 1
	out += str(ans) + '\n'
print(out)


import sys
input = sys.stdin.readline
from array import array

def solve():
	n = int(input())
	s = input().rstrip()
	count = 0
	for i in range(0, len(s), 2):
		if s[i] != s[i + 1]:
			count += 1
	return count
for _ in range(int(input())):
	print(solve())


from sys import stdin, stdout
import collections
import math

def solve():
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		i = 0
		ans = 0
		while i < n:
			c = 0
			p = s[i]
			while i < n and s[i] == p:
				i += 1
				c += 1
			if c % 2 == 1:
				ans += 1
				i += 1
		print(ans)
	return
input = stdin.readline
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	p = s[0]
	c = 0
	t = 1
	for i in range(1, n):
		if s[i] == p:
			t += 1
		elif t & 1:
			c += 1
			p = s[i - 1]
			t += 1
		else:
			p = s[i]
			t = 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	count = 0
	while i < n - 1:
		if s[i] != s[i + 1]:
			count += 1
		i += 2
	print(count)


n = int(input())
datas = []
for i in range(n):
	t = int(input())
	data = list(map(int, input()))
	datas.append(data)

def solve(data):
	c = 0
	for i in range(0, int(len(data)), 2):
		if data[i] != data[i + 1]:
			c += 1
	print(c)
for d in datas:
	solve(d)


n = int(input())
while n:
	n -= 1
	dlch = int(input())
	ch = input()
	count = 0
	for i in range(1, dlch, 2):
		if ch[i] != ch[i - 1]:
			count += 1
	print(count)


inp1 = int(input())
for i in range(inp1):
	inp2 = int(input())
	inp3 = input()
	count = 0
	for j in range(0, inp2, 2):
		if inp3[j] != inp3[j + 1]:
			count += 1
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	a = input()
	count = 0
	for i in range(0, n - 1, 2):
		if a[i] != a[i + 1]:
			count += 1
	print(count)
	t -= 1


def comparision(a):
	b = len(a)
	c = 0
	for i in range(0, b, 2):
		if a[i] != a[i + 1]:
			c = c + 1
	return c
for _ in range(int(input())):
	a = int(input())
	b = input()
	c = comparision(b)
	print(c)


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


def countminstep(x):
	c = 0
	lst = []
	for y in range(0, len(x), 2):
		if y <= len(x) - 2:
			lst.append(x[y:y + 2])
		else:
			break
	for z in range(0, len(lst)):
		if lst[z][0] not in lst[z][1]:
			c += 1
	return c
n = int(input())
lst_2 = []
lst_3 = []
for m in range(0, n):
	g = int(input())
	lst_3.append(g)
	h = input()
	lst_2.append(h)
for k in range(0, n):
	d = lst_2[k]
	print(countminstep(d))


test_cases = int(input(''))
tests_list = []
for _ in range(0, test_cases):
	len_of_s = int(input(''))
	s_binary = input('')
	tests_list.append(s_binary)
for s_binary in tests_list:
	upper_limit = len(s_binary) / 2
	upper_limit = int(upper_limit)
	value = 0
	i = 0
	for index in range(0, upper_limit):
		if s_binary[0 + i] != s_binary[1 + i]:
			value += 1
		i += 2
	print(value)


for t in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			c += 1
	print(c)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	arr = []
	prev = s[0]
	cnt = 0
	ops = 0
	for i in range(n):
		if prev == s[i]:
			cnt += 1
		else:
			if arr:
				if arr[-1] % 2 == 1:
					ops += 1
					if cnt == 1:
						cnt = arr.pop() + 2
					else:
						if arr[-1] == 1:
							arr[-1] += cnt
						else:
							arr[-1] += 1
							arr.append(cnt - 1)
						cnt = 1
					prev = s[i]
					continue
			arr.append(cnt)
			prev = s[i]
			cnt = 1
	if arr and arr[-1] % 2 == 1:
		ops += 1
	return ops
for _ in range(int(input())):
	print(solve())


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		(a, b) = (0, 0)
		ans = 0
		for c in s:
			if c == '1':
				a += 1
				if b % 2 == 1:
					ans += 1
					a += 1
					b = 0
			elif c == '0':
				b += 1
				if a % 2 == 1:
					ans += 1
					b += 1
					a = 0
		print(ans)
main()


for n in [*open(0)][2::2]:
	q = 0
	r = 0
	for i in range(len(n) - 2):
		if n[i] != n[i + 1]:
			r += (i + 1) % 2
	print(r)


def foo(n: int, s: str) -> int:
	(prev_ch, prev_len) = ('', 0)
	res = 0
	for ch in s:
		if ch == prev_ch:
			prev_len += 1
			continue
		if prev_len % 2 == 0:
			prev_ch = ch
			prev_len = 1
		else:
			prev_ch = ch
			prev_len = 2
			res += 1
		pass
	return res
T = int(input())
for _case in range(T):
	n = int(input())
	s = input()
	print(foo(n, s))


def solve():
	n = int(input())
	s = input()
	k = list(s)
	ans = 0
	for i in range(1, n, 2):
		if s[i] != s[i - 1]:
			ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


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


def solve():
	n = int(input())
	s = list(input())
	count = 1
	answer = 0
	prev = s[0]
	for i in range(1, n):
		if s[i] == prev:
			count += 1
		elif count % 2 == 0:
			prev = s[i]
			count = 1
		else:
			s[i] = prev
			count += 1
			answer += 1
	return answer
t = int(input())
for _ in range(t):
	print(solve())


def solve() -> int:
	n = int(input())
	string = input()
	segments = []
	last = None
	counter = 0
	for char in string:
		if char == last:
			counter += 1
		else:
			if last is not None:
				segments.append(counter)
			counter = 1
		last = char
	segments.append(counter)
	result = 0
	for index in range(len(segments)):
		if segments[index] % 2 == 1:
			result += 1
			segments[index] -= 1
			segments[index + 1] += 1
	return result
results = []
for _ in range(int(input())):
	results.append(str(solve()))
print('\n'.join(results))


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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	c = input()
	total = 1
	val = 0
	for i in range(1, n):
		if c[i] != c[i - 1]:
			if total % 2:
				val += 1
				total = 0
			else:
				total = 1
		else:
			total += 1
	print(val)


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	res = 0
	nb0 = 0
	nb1 = 0
	start = s[0]
	if start == '0':
		nb0 = 1
	else:
		nb1 = 1
	for i in range(1, n):
		if s[i] == start:
			if s[i] == '0':
				nb0 += 1
			else:
				nb1 += 1
		elif (nb0 + nb1) % 2 == 0:
			start = s[i]
			if start == '0':
				nb0 = 1
			else:
				nb1 = 1
		else:
			res += 1
			if i != n - 1:
				start = s[i + 1]
				nb1 = 0
				nb0 = 0
	print(res)


from itertools import *
for s in [*open(0)][2::2]:
	a = [i for (i, (k, g)) in enumerate(groupby(s[:-1])) if len([*g]) & 1]
	print(sum((y - x for (x, y) in zip(a[::2], a[1::2]))))


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	Answer = 0
	INPUT = int(input())
	STRINPUT = input()
	for i in range(0, INPUT, 2):
		if STRINPUT[i] + STRINPUT[i + 1] == '01' or STRINPUT[i] + STRINPUT[i + 1] == '10':
			Answer += 1
	print(Answer)


for zzzzz in range(int(input())):
	n = int(input())
	a = input()
	count = 0
	for i in range(0, n, 2):
		f = a[i]
		s = a[i + 1]
		if f != s:
			count = count + 1
	print(count)


t1 = int(input())
for hi in range(t1):
	n = int(input())
	s = str(input())
	p = 0
	o = True
	l = 1
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			p += 1
		elif o:
			c = s[i]
			o = False
		elif c != s[i]:
			l += 1
			c = s[i]
	print(p)


t = int(input())
for i in range(t):
	tc = int(input())
	inp = input()
	cnt = 0
	for j in range(0, len(inp), 2):
		if inp[j] != inp[j + 1]:
			cnt += 1
	print(cnt)


def contar(pal):
	cont = 0
	for i in range(0, len(pal), 2):
		bi = pal[i:i + 2]
		if bi == '01' or bi == '10':
			cont += 1
	return cont
for _ in range(int(input())):
	input()
	pal = input()
	print(contar(pal))


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	j = 0
	c = 0
	while m > 0:
		if s[j] != s[j + 1]:
			c += 1
		m -= 2
		j += 2
	print(c)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	input()
	inp += [input()]
case = 0
for i in inp:
	case += 1
	a = []
	l = 0
	char = ''
	for c in i:
		if char != c:
			if l > 0:
				a.append(l)
			char = c
			l = 1
		else:
			l += 1
	a.append(l)
	curr_odd = False
	d = 0
	s = 0
	for i in a:
		if i % 2 == 1:
			if curr_odd:
				s += d
				curr_odd = False
			else:
				curr_odd = True
				d = 1
		elif curr_odd:
			d += 1
	print(str(s))


n = int(input(''))
t = 0
while t < n:
	t += 1
	length = int(input(''))
	s = input('')
	count = 0
	for i in range(1, length, 2):
		if s[i] != s[i - 1]:
			count += 1
	print(count)


def solve():
	n = int(input())
	s = input()
	p = 0
	i = 1
	res = 0
	while i < n:
		if s[i] != s[p]:
			if (i - p) % 2 == 1:
				res += 1
				p = i + 1
			else:
				p = i
		i += 1
	print(res)
t = int(input())
while t > 0:
	t -= 1
	solve()


for i in range(int(input())):
	a = input()
	a = input()
	b = 0
	for i in range(len(a) // 2):
		if a[i * 2] != a[i * 2 + 1]:
			b += 1
	print(b)


def fun(ans):
	i = 0
	c = 0
	for _ in range(len(ans) // 2):
		if ans[i] != ans[i + 1]:
			c += 1
		i += 2
	return c
for _ in range(int(input())):
	x = input()
	arr = input()
	x = fun(arr)
	print(x)


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


t = int(input())

def solve():
	n = int(input())
	s = input()
	count = 0
	for i in range(0, len(s), 2):
		count += 1 if s[i] != s[i + 1] else 0
	print(count)
while t:
	solve()
	t -= 1


a = int(input())
for _ in range(a):
	b = int(input())
	c = input()
	count = 0
	counter = 1
	for x in c[::2]:
		if x == '1' and c[counter] == '0' or (x == '0' and c[counter] == '1'):
			count += 1
		counter += 2
	print(count)


for _ in range(int(input())):
	(n, s, w) = (int(input()), input(), 0)
	print(sum([1 for i in range(1, n, 2) if s[i] != s[i - 1]]))


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	tik = 0
	cursor = s[0]
	for i in range(n):
		if cursor == s[i]:
			tik += 1
		else:
			if tik % 2 != 0:
				count += 1
				tik = 0
			else:
				tik = 1
			cursor = '1' if cursor == '0' else '0'
	print(count)


for t in range(int(input())):
	n = int(input())
	s = input()
	swap = 0
	for i in range(n):
		if i % 2 == 0:
			a = s[i]
			continue
		elif a == s[i]:
			continue
		else:
			swap += 1
	print(swap)


def read_input():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		out = good(s)
		print(out)

def good(s):
	total_ops = 0
	swapper = {'1': '0', '0': '1'}
	s += swapper[s[-1]]
	current = s[0]
	length = 0
	is_odd = False
	seg_count = 0
	for c in s:
		if c == current:
			length += 1
		else:
			if length % 2 != 0:
				if is_odd:
					total_ops += seg_count
					seg_count = 0
					is_odd = False
				else:
					is_odd = True
			if is_odd:
				seg_count += 1
			current = swapper[current]
			length = 1
	return total_ops
read_input()


for t in range(int(input())):
	n = int(input())
	s = input()
	count = 1
	ops = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			if count % 2 != 0:
				count = 2
				ops += 1
			else:
				count = 1
		else:
			count += 1
	print(ops)


def minimumToMakeEven(bin_nums, n):
	change = 0
	count_curr = 0
	i = 0
	while i < n:
		curr_char = bin_nums[i]
		while i < n and bin_nums[i] == curr_char:
			count_curr += 1
			i += 1
		if count_curr % 2:
			bin_nums[i] = curr_char
			change += 1
			i += 1
		count_curr = 0
	print(change)
t = int(input())
for _ in range(t):
	n = int(input())
	bin_string = input()
	minimumToMakeEven(list(bin_string), n)


for _ in range(int(input())):
	input()
	s = input()
	prev_char = s[0]
	count = 0
	ans = 0
	for i in s:
		if i == prev_char:
			count += 1
		else:
			if count % 2:
				ans += 1
				count = 0
			else:
				count = 1
			prev_char = i
	if count % 2:
		ans += 1
	print(ans)


t = int(input())
for T in range(t):
	s = int(input())
	a = list(map(len, input().replace('10', '1 0').replace('01', '0 1').split()))
	picked = False
	g = 0
	for i in a:
		if i % 2 and picked:
			picked = False
		elif i % 2:
			g += 1
			picked = True
		elif picked:
			g += 1
	print(g)


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


for i in range(int(input())):
	n = int(input(''))
	str1 = input()
	counter = 0
	for j in range(0, n, 2):
		if str1[j] != str1[j + 1]:
			counter += 1
	print(counter)


a = int(input())
for i in range(0, a):
	n = int(input())
	r = str(input())
	s = 0
	k = 1
	for j in range(0, n - 1):
		if r[j] == r[j + 1]:
			k = k + 1
		elif k % 2 == 1:
			j = j + 1
			s = s + 1
			k = 0
		else:
			k = 1
	print(s)


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	s = rs()
	a = []
	curr = 0
	last = s[0]
	for i in range(n):
		if s[i] == last:
			curr += 1
		else:
			a.append(curr)
			last = s[i]
			curr = 1
	a.append(curr)
	ans = 0
	for i in range(len(a) - 1):
		if a[i] % 2:
			ans += 1
			a[i + 1] += 1
	print(ans)


cases = int(input())

def do():
	_ = int(input())
	s = input()
	new_s = list(s)
	number_of_changes = 0
	for i in range(0, len(s), 2):
		if s[i] != s[i + 1]:
			number_of_changes += 1
			new_s[i + 1] = s[i]
	print(number_of_changes)
for i in range(cases):
	do()


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


t = int(input())
for i in range(t):
	n = int(input())
	lst = input()
	ans = 0
	for j in range(0, n - 1, 2):
		if lst[j] + lst[j + 1] == '10' or lst[j] + lst[j + 1] == '01':
			ans += 1
	print(ans)


for testcases in range(int(input())):
	a1 = input()
	need = 0
	a = [i for i in input()]
	for i in range(0, int(a1) - 1, 2):
		if a[i] != a[i + 1]:
			need += 1
	print(need)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(0, n, 2):
		if s[i:i + 2] == '10' or s[i:i + 2] == '01':
			ans += 1
	print(ans)


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))
for ii in range(int(input())):
	n = int(input())
	s = input()
	r = 0
	for i in range(0, n, 2):
		if s[i] != s[i + 1]:
			r += 1
	print(r)


n = int(input())
for i in range(n):
	temp = int(input())
	arr = str(input())
	res = 0
	j = 0
	while j < temp - 1:
		if arr[j] != arr[j + 1]:
			res += 1
		j += 2
	print(res)


t = int(input())
for k in range(t):
	n = int(input())
	s = input()
	cnt = 0
	i = 1
	d = 1
	while i < n:
		if s[i] != s[i - 1]:
			if d % 2 == 0:
				d = 1
				i += 1
			else:
				cnt += 1
				d = 1
				i += 2
		else:
			d += 1
			i += 1
	print(cnt)


def helper():
	tstcs = int(input())
	for i in range(tstcs):
		n = int(input())
		s = input()
		cnt = 0
		oddsm = 0
		evensm = 0
		if s[0] == '0':
			evensm += 1
		else:
			oddsm += 1
		for i in range(1, n):
			if s[i] == '0':
				if s[i - 1] == '1' and oddsm % 2 == 1:
					cnt += 1
					s[i] == '1'
					oddsm = 0
				else:
					evensm += 1
			elif s[i - 1] == '0' and evensm % 2 == 1:
				cnt += 1
				s[i] == '1'
				evensm = 0
			else:
				oddsm += 1
		print(cnt)
helper()


import re
for s in [*open(0)][2::2]:
	i = p = r = 0
	for t in re.findall('0+|1+', s):
		i += 1
		if len(t) & 1:
			if p:
				r += i - p
				p = 0
			else:
				p = i
	print(r)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = s[0]
	c = 1
	ans = 0
	for el in s[1:]:
		if el != p:
			if c % 2:
				ans += 1
				c += 1
			else:
				p = el
				c = 1
		else:
			c += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	i = 0
	count = 0
	while i < n:
		if a[i:i + 2] == ['1', '1'] or a[i:i + 2] == ['0', '0']:
			i += 2
		else:
			count += 1
			i += 2
	print(count)