You are given a binary string S of length N (i.e. every character of S is either 0 or 1).

You can perform the following operation on S:
select any two indices i, j of the same parity, i.e. either both i, j are odd or both i, j are even
swap S_{i} and S_{j}

For example, in the string 1110, we can swap the second and the fourth characters to get 1011. However, we can never obtain 1101 from 1110 by performing such swaps.

Find the maximum possible number of occurrences of the string 01 as a [substring] of S after performing the above operation any number of times (it is also allowed to not perform any operation).

For example, the string 1110 has no occurrence of the string 01 as a substring, whereas we can swap the second and fourth characters to obtain 1{\color{red}{01}}1 which has exactly one occurrence of 01 (colored red).

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of testcases. The description of the T testcases follow.
- Each testcase consists of two lines.
- The first line contains a single integer N, the length of the string S.
- The second line contains a binary string of length N.

------ Output Format ------ 

- For each testcase, print in a single line, an integer — the answer as per the problem statement.

------ Constraints ------ 

$1 ≤ T ≤ 4000$
$1 ≤ |S| ≤ 10^{5}$
- The sum of $|S|$ over all testcases doesn't exceed $10^{5}$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
5
00100
5
01010
5
10001
----- Sample Output 1 ------ 
1
2
2
----- explanation 1 ------ 
Test case $1$: The only strings that can be obtained by performing the given operations are $\{10000, 00100, 00001\}$. Of these the two strings $0{\color{red}{01}}00$ and $000{\color{red}{01}}$ contain exactly one occurrence of $01$.

Test case $2$: The given string $S$ cannot be changed by performing the given operation and contains $2$ occurrences of the string $01$, i.e. ${\color{red}01}{\color{blue}01}0$.

Test case $3$: The only strings that can be obtained by performing the given operations are $\{00101, 10001, 10100\}$. The string $0{\color{red}{01}}{\color{blue}{01}}$ contains two occurrences of $01$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


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

def st():
	return input().rstrip('\n')

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

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

def solve(lent, binn):
	evens = binn[1::2]
	odds = binn[::2]
	odds0 = odds.count('0')
	odds1 = odds.count('1')
	evens0 = evens.count('0')
	evens1 = evens.count('1')
	val1 = min(odds0, evens1)
	x = lent & 1
	valid = max(0, lent // 2 - val1 - 1 + x)
	val2 = min(odds1, evens0)
	ans = val1 + min(valid, val2)
	return ans

def main():
	for i in range(inp()):
		print(solve(inp(), st()))
main()


for _ in range(int(input())):
	n = int(input())
	l = str(input())
	ans = 0
	a = l.count('1')
	b = n - a
	for i in range(1, n):
		if l[i - 1] == '0' and l[i] == '1':
			ans += 1
	ans = max(ans, min(a, b) - int(a == b))
	print(ans)


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

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	s = ip()
	o1 = o2 = z1 = z2 = 0
	i = 0
	a = s.count('1')
	b = s.count('0')
	string = '01' * (n // 2)
	if s == string:
		print(n // 2)
	elif a < b:
		print(a)
	elif b < a:
		print(b)
	else:
		print(a - 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	b = s.count('0')
	string = '01' * (n // 2)
	if s == string:
		print(n // 2)
	elif a < b:
		print(a)
	elif b < a:
		print(b)
	else:
		print(a - 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = s.count('1')
	b = s.count('0')
	x = ''
	s1 = ''
	for j in range(1, n + 1):
		if j % 2 == 0:
			x = '1'
		else:
			x = '0'
		s1 += x
	if s == s1:
		print(s.count('01'))
	elif a < b:
		print(a)
	elif b < a:
		print(b)
	else:
		print(a - 1)


def merge(e, o):
	n = len(e)
	m = len(o)
	s = ''
	for i in range(m):
		s += e[i] + o[i]
	if n > m:
		s += e[n - 1]
	return s

def count01(s):
	zero = 0
	cnt = 0
	for x in s:
		if x == '0':
			zero = 1
		elif zero == 1:
			zero = 0
			cnt += 1
	return cnt
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip()
	odd_pos = n // 2
	even_pos = n - odd_pos
	even_0s = 0
	even_1s = 0
	odd_0s = 0
	odd_1s = 0
	for i in range(0, n, 2):
		if s[i] == '1':
			even_1s += 1
		else:
			even_0s += 1
	for i in range(1, n, 2):
		if s[i] == '1':
			odd_1s += 1
		else:
			odd_0s += 1
	pair = 0
	even_s = '0' * even_0s + '1' * even_1s
	odd_s = '1' * odd_1s + '0' * odd_0s
	s = merge(even_s, odd_s)
	a = count01(s)
	even_s = '0' * even_0s + '1' * even_1s
	odd_s = '0' * odd_0s + '1' * odd_1s
	s = merge(even_s, odd_s)
	b = count01(s)
	even_s = '1' * even_1s + '0' * even_0s
	odd_s = '0' * odd_0s + '1' * odd_1s
	s = merge(even_s, odd_s)
	c = count01(s)
	even_s = '1' * even_1s + '0' * even_0s
	odd_s = '1' * odd_1s + '0' * odd_0s
	s = merge(even_s, odd_s)
	d = count01(s)
	print(max(a, b, c, d))


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	a = S.count('1')
	b = S.count('0')
	x = ''
	S1 = ''
	for j in range(1, N + 1):
		if j % 2 == 0:
			x = '1'
		else:
			x = '0'
		S1 += x
	if S == S1:
		print(S.count('01'))
	elif a < b:
		print(a)
	elif b < a:
		print(b)
	else:
		print(a - 1)


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		(t1, t0) = (0, 0)
		check = True
		if n % 2 == 0:
			for i in range(0, n - 1, 2):
				if s[i] != '0' or s[i + 1] != '1':
					check = False
					break
			if check:
				print(n // 2)
				continue
		for i in s:
			if i == '0':
				t0 += 1
			else:
				t1 += 1
		if t0 == t1:
			print(t0 - 1)
		else:
			print(min(t0, t1))
except:
	pass


cases = int(input())
for t in range(cases):
	N = int(input())
	S = input()
	even = []
	odd = []
	merged_list = [None] * len(S)
	for i in range(len(S)):
		if i % 2 == 0:
			even.append(S[i])
		else:
			odd.append(S[i])

	def merge(even, odd, merged_list):
		merged_list[::2] = even
		merged_list[1::2] = odd
		return count(merged_list)

	def count(merged_list):
		count = 0
		for j in range(len(S) - 1):
			if merged_list[j] == '0' and merged_list[j + 1] == '1':
				count += 1
		return count
	even.sort()
	odd.sort(reverse=True)
	m1 = merge(even, odd, merged_list)
	odd.reverse()
	m2 = merge(even, odd, merged_list)
	even.reverse()
	m3 = merge(even, odd, merged_list)
	odd.reverse()
	m4 = merge(even, odd, merged_list)
	print(max(m1, m2, m3, m4))


def initializer(s, n):
	ev = 0
	od = 0
	evones = 0
	odones = 0
	for idx in range(n):
		if (idx + 1) % 2 == 0:
			if s[idx] == '0':
				ev += 1
			else:
				evones += 1
		elif s[idx] == '0':
			od += 1
		else:
			odones += 1
	check = True
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if s[i] != '0' or s[i + 1] != '1':
				check = False
				break
		if check:
			return n // 2
	ans = min(odones + evones, od + ev)
	if odones + evones == od + ev:
		return ans - 1
	else:
		return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(initializer(s, n))


def find_number_of_characters_at_odd_and_even_positions(string, character):
	odd_counts = even_counts = 0
	for (index, element) in enumerate(string):
		if (index + 1) % 2 == 0:
			if character == element:
				even_counts += 1
		elif character == element:
			odd_counts += 1
	return (odd_counts, even_counts)

def find_number_of_pairs(string):
	(zero_odd, zero_even) = find_number_of_characters_at_odd_and_even_positions(string, '0')
	(one_odd, one_even) = find_number_of_characters_at_odd_and_even_positions(string, '1')
	pairs = 0
	odd_even_pairs = min(zero_odd, one_even)
	pairs += odd_even_pairs
	zero_odd = zero_odd - odd_even_pairs
	one_even = one_even - odd_even_pairs
	if zero_odd > 0:
		zero_odd = zero_odd - 1
		even_odd_pair = min(zero_even, one_odd)
		pairs += even_odd_pair
	elif one_odd > 0:
		one_odd -= 1
		even_odd_pair = min(zero_even, one_odd)
		pairs += even_odd_pair
	return pairs
test_cases = int(input())
for case in range(test_cases):
	length = input()
	string = input()
	no_of_pairs = find_number_of_pairs(string)
	print(no_of_pairs)


def merge(e, o, N):
	string = ''
	k = 0
	l = 0
	for i in range(N):
		if i % 2 == 0:
			string += e[k]
			k += 1
		else:
			string += o[l]
			l += 1
	return string

def operation(S, N):
	even_string = ''
	odd_string = ''
	for i in range(N):
		if i % 2 == 0:
			even_string = even_string + S[i]
		else:
			odd_string = odd_string + S[i]
	e = sorted(even_string)
	o = sorted(odd_string)
	a = merge(e, o, N)
	e = sorted(even_string)
	o = sorted(odd_string, reverse=True)
	b = merge(e, o, N)
	e = sorted(even_string, reverse=True)
	o = sorted(odd_string)
	c = merge(e, o, N)
	e = sorted(even_string, reverse=True)
	d = merge(e, o, N)
	o = sorted(odd_string, reverse=True)
	return max(a.count('01'), b.count('01'), c.count('01'), d.count('01'))
t = int(input())
while t > 0:
	N = int(input())
	S = input()
	n = operation(S, N)
	print(n)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	p = [[0, 0], [0, 0]]
	for (i, x) in enumerate(input()):
		p[i & 1][int(x)] += 1
	a = min(p[0][0], p[1][1])
	b = min(max(0, n // 2 - a - int(n & 1 == 0)), min(p[1][0], p[0][1]))
	print(a + b)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = [[0, 0], [0, 0]]
	o = [0, 0]
	e = [0, 0]
	for i in range(n):
		p[i & 1][int(s[i])] += 1
	for i in range(0, n, 2):
		e[int(s[i])] += 1
	for i in range(1, n, 2):
		o[int(s[i])] += 1
	a = min(p[0][0], p[1][1])
	b = min(max(0, n // 2 - a - int(n & 1 == 0)), min(p[1][0], p[0][1]))
	print(a + b)


from sys import stdin
input = stdin.readline
T = int(input())
for tx in range(T):
	N = int(input())
	par = 0
	prof = {'0': [0, 0], '1': [0, 0]}
	for c in input().strip():
		prof[c][par] += 1
		par = 1 - par
	pat = min(prof['0'][0], prof['1'][1])
	if prof['0'][0] == prof['1'][1] and prof['1'][0] > 0:
		prof['1'][0] -= 1
	pat += min(prof['0'][1], prof['1'][0])
	print(pat)


try:
	for _ in range(int(input())):
		N = int(input())
		S = input()
		(x2, x1) = (0, 0)
		ans = True
		if N % 2 == 0:
			for i in range(0, N - 1, 2):
				if S[i] != '0' or S[i + 1] != '1':
					ans = False
					break
			if ans:
				print(N // 2)
				continue
		for i in S:
			if i == '0':
				x1 += 1
			else:
				x2 += 1
		if x1 == x2:
			print(x1 - 1)
			continue
		print(min(x1, x2))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('0')
	b = s.count('1')
	if n % 2 != 0:
		print(min(b, a))
	else:
		c = 0
		for i in range(0, n - 1):
			if s[i] == '0' and s[i + 1] == '1':
				c = c + 1
		m = min(b, a)
		if m < n // 2:
			print(max(c, m))
		else:
			print(max(m - 1, c))


def mer_con(even, odd):
	st = ''
	for i in range(max(len(even), len(odd))):
		if i < len(even):
			st += str(even[i])
		if i < len(odd):
			st += str(odd[i])
	return st.count('01')
for _ in range(int(input())):
	n = int(input())
	data = input()
	even = [int(data[i]) for i in range(0, n, 2)]
	odd = [int(data[i]) for i in range(1, n, 2)]
	even.sort()
	odd.sort()
	merge_count = mer_con(even, odd)
	even.sort(reverse=True)
	odd.sort()
	temp = mer_con(even, odd)
	if merge_count < temp:
		merge_count = temp
	even.sort(reverse=True)
	odd.sort(reverse=True)
	temp = mer_con(even, odd)
	if merge_count < temp:
		merge_count = temp
	even.sort()
	odd.sort(reverse=True)
	temp = mer_con(even, odd)
	if merge_count < temp:
		merge_count = temp
	print(merge_count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	b = []
	for i in range(n):
		if i % 2 == 0:
			a.append(s[i])
		else:
			b.append(s[i])
	a0 = a.count('0')
	b0 = b.count('0')
	a1 = a.count('1')
	b1 = b.count('1')
	if a0 > b1:
		print(b1 + min(b0, a1))
	else:
		print(a0 + min(b0, max(0, a1 - 1)))


def count(l1, l2):
	l = []
	m = min(len(l1), len(l2))
	for i in range(m):
		l.append(l1[i])
		l.append(l2[i])
	if len(l1) != len(l2):
		if m == len(l1):
			l += l2[m:]
		else:
			l += l1[m:]
	s = ''.join(l)
	c = s.count('01')
	return c
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	e = [s[i] for i in range(n) if i % 2 == 0]
	o = [s[i] for i in range(n) if i % 2 != 0]
	c1 = count(sorted(e), sorted(o))
	c2 = count(sorted(e, reverse=True), sorted(o))
	c3 = count(sorted(e), sorted(o, reverse=True))
	c4 = count(sorted(e, reverse=True), sorted(o, reverse=True))
	print(max([c1, c2, c3, c4]))


def merge(a, b):
	c = []
	i = 0
	j = 0
	while i < len(a) or j < len(b):
		if i < len(a):
			c.append(a[i])
		if j < len(b):
			c.append(b[j])
		i += 1
		j += 1
	ans = 0
	for i in range(0, len(c) - 1):
		if c[i] == 0 and c[i + 1] == 1:
			ans += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	s = input()
	ev = []
	od = []
	ans = 0
	for i in range(0, n):
		if i % 2 == 0:
			ev.append(int(s[i]))
		else:
			od.append(int(s[i]))
	ev.sort()
	od.sort()
	evr = ev[::-1]
	odr = od[::-1]
	s1 = merge(ev, od)
	s2 = merge(ev, odr)
	s3 = merge(evr, odr)
	s4 = merge(evr, od)
	ans = max(s1, s2, s3, s4)
	print(ans)


t = int(input())

def merge(odd, even):
	ol = len(odd)
	el = len(even)
	l = []
	for i in range(max(ol, el)):
		if i < el:
			l.append(even[i])
		if i < ol:
			l.append(odd[i])
	return ''.join(l)
while t:
	n = int(input())
	s = input()
	odd = []
	even = []
	for i in range(n):
		if i % 2:
			odd.append(s[i])
		else:
			even.append(s[i])
	odd.sort()
	even.sort()
	l = merge(odd, even)
	c1 = l.count('01')
	l = merge(odd[::-1], even)
	c2 = l.count('01')
	l = merge(odd, even[::-1])
	c3 = l.count('01')
	l = merge(odd[::-1], even[::-1])
	c4 = l.count('01')
	print(max(c1, c2, c3, c4))
	t -= 1


def merge(even, odd):
	ans = ''
	lenE = len(even)
	lenO = len(odd)
	for i in range(lenE):
		ans += even[i]
		if i < lenO:
			ans += odd[i]
	return ans

def count(s):
	ans = 0
	index = 0
	n = len(s)
	while index + 1 < n:
		if s[index] == '0' and s[index + 1] == '1':
			index += 2
			ans += 1
		else:
			index += 1
	return ans
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	odd = []
	even = []
	for i in range(n):
		if i % 2:
			odd.append(s[i])
		else:
			even.append(s[i])
	even.sort()
	odd.sort(reverse=True)
	m1 = merge(even, odd)
	odd.reverse()
	m2 = merge(even, odd)
	even.reverse()
	m3 = merge(even, odd)
	odd.reverse()
	m4 = merge(even, odd)
	print(max(count(m1), count(m2), count(m3), count(m4)))


t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip()
	check = True
	t0 = 0
	t1 = 0
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if s[i] != '0' or s[i + 1] != '1':
				check = False
				break
		if check:
			print(n // 2)
			continue
	for i in s:
		if i == '0':
			t0 += 1
		else:
			t1 += 1
	if t0 == t1:
		print(t1 - 1)
		continue
	print(min(t0, t1))


def merge(odd, even):
	l = len(odd)
	z = ''
	for j in range(l):
		z = z + odd[j]
		if j < len(even):
			z = z + even[j]
	return z

def count(m):
	return m.count('01')
for _ in range(int(input())):
	n = int(input())
	str = input()
	odd = []
	even = []
	for i in range(n):
		if i % 2:
			even.append(str[i])
		else:
			odd.append(str[i])
	odd.sort()
	even.sort(reverse=True)
	m1 = merge(odd, even)
	odd.reverse()
	even.reverse()
	m2 = merge(odd, even)
	print(max(count(m1), count(m2)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	s = list(map(int, list(s)))
	(n0, n1) = (len(s) - sum(s), sum(s))
	c = 0
	for i in range(0, len(s) - 1, 2):
		if s[i:i + 2] == [0, 1]:
			c += 1
	if n0 == n1:
		print(max(c, n0 - 1))
	elif n0 < n1:
		print(n0)
	else:
		print(n1)


def joinf(x, x1):
	r = len(x) + len(x1)
	w = 0
	w1 = 0
	q = ''
	for i in range(r):
		if i % 2 == 0:
			q += x[w]
			w += 1
		else:
			q += x1[w1]
			w1 += 1
	return q.count('01')
for j in range(int(input())):
	n = int(input())
	l = input()
	e = ''
	o = ''
	for i in range(n):
		if i % 2 == 0:
			e += l[i]
		else:
			o += l[i]
	e = sorted(e)
	o = sorted(o)
	test1 = joinf(e, o)
	test2 = joinf(e, o[::-1])
	test3 = joinf(e[::-1], o)
	test4 = joinf(e[::-1], o[::-1])
	print(max(test1, test2, test3, test4))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	x = s.count('0')
	y = s.count('1')
	a = ''
	z = ''
	for i in range(1, n + 1):
		if i % 2 == 0:
			a = '1'
		else:
			a = '0'
		z += a
	if s == z:
		print(s.count('01'))
	elif x < y:
		print(x)
	elif x > y:
		print(y)
	else:
		print(x - 1)


def count(s):
	cou = 0
	for i in range(len(s) - 1):
		if s[i] == '0' and s[i + 1] == '1':
			cou += 1
	return cou

def merge(odd, even):
	s = ''
	en = len(even)
	on = len(odd)
	for i in range(en):
		s += even[i]
		if i < on:
			s += odd[i]
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	odd = []
	even = []
	for i in range(n):
		if i % 2 == 0:
			even.append(s[i])
		else:
			odd.append(s[i])
	even.sort()
	odd.sort(reverse=True)
	s1 = merge(odd, even)
	odd.reverse()
	s2 = merge(odd, even)
	even.reverse()
	s3 = merge(odd, even)
	odd.reverse()
	s4 = merge(odd, even)
	print(max(count(s1), count(s2), count(s3), count(s4)))


import math
import bisect
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

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

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def solve(even, odd, n):
	count = 0
	while even and odd and (even[0] == '0') and (odd[0] == '1'):
		count += 1
		even.pop(0)
		odd.pop(0)
	if even and odd and (even[-1] == '1') and (odd[-1] == '0'):
		while even and odd and (even[-1] == '1') and (odd[-1] == '0'):
			count += 1
			even.pop()
			odd.pop()
		return count - (1 if not even else 0)
	else:
		return count

def process(arr, n):
	(odd, even) = ([], [])
	for i in range(0, n, 2):
		even.append(arr[i])
	for i in range(1, n, 2):
		odd.append(arr[i])
	even.sort()
	odd.sort(reverse=True)
	return solve(even, odd, n)

def main():
	for _ in range(int(input())):
		N = intin()
		arr = list(input())
		print(process(arr, N))
main()


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		string = input()
		(t1, t0) = (0, 0)
		check = True
		if n % 2 == 0:
			for i in range(0, n - 1, 2):
				if string[i] != '0' or string[i + 1] != '1':
					check = False
					break
			if check:
				print(n // 2)
				continue
		for i in string:
			if i == '0':
				t0 += 1
			else:
				t1 += 1
		if t1 == t0:
			a = t1 - 1
			print(a)
			continue
		print(min(t1, t0))
except:
	pass


for t in range(int(input())):
	N = int(input())
	S = input()
	ungerade = [S[i] for i in range(N) if i % 2 == 0]
	gerade = [x for (i, x) in enumerate(S) if i % 2 == 1]
	anz_0_ungerade = ungerade.count('0')
	anz_1_ungerade = ungerade.count('1')
	anz_0_gerade = gerade.count('0')
	anz_1_gerade = gerade.count('1')
	nullen = S.count('0')
	einsen = S.count('1')
	if nullen == einsen:
		if anz_0_gerade == 0:
			solution = N / 2
		else:
			solution = N / 2 - 1
	else:
		solution = min(nullen, einsen)
	print(int(solution))


for _ in range(int(input())):
	size = int(input())
	inputList = input()
	odd_parity = []
	even_parity = []
	for i in range(0, size):
		if i % 2 == 0:
			even_parity.append(inputList[i])
		else:
			odd_parity.append(inputList[i])
	even_parity.sort()
	odd_parity.sort()
	poss1 = ''
	poss2 = ''
	poss3 = ''
	(j, k) = (0, 0)
	for i in range(0, size):
		if i % 2 == 0:
			poss1 += even_parity[j]
			poss2 += even_parity[j]
			poss3 += even_parity[len(even_parity) - 1 - j]
			j += 1
		else:
			poss1 += odd_parity[k]
			poss2 += odd_parity[len(odd_parity) - 1 - k]
			poss3 += odd_parity[k]
			k += 1
	ans = max(poss1.count('01'), poss2.count('01'), poss3.count('01'))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	odd = []
	even = []
	for i in range(0, len(s), 2):
		even.append(s[i])
		if i + 1 < len(s):
			odd.append(s[i + 1])
	even.sort()
	odd.sort(reverse=True)
	c1 = ''
	(j, k) = (0, 0)
	for i in range(len(s)):
		if i % 2 == 0:
			c1 += even[j]
			j += 1
		else:
			c1 += odd[k]
			k += 1
	s1 = c1.count('01')
	odd.sort()
	even.sort(reverse=True)
	c1 = ''
	(j, k) = (0, 0)
	for i in range(len(s)):
		if i % 2 == 0:
			c1 += even[j]
			j += 1
		else:
			c1 += odd[k]
			k += 1
	s2 = c1.count('01')
	print(max(s1, s2))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	m = s.count('01')
	arr = list(s.split())
	check = True
	t0 = 0
	t1 = 0
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if s[i] != '0' or s[i + 1] != '1':
				check = False
				break
		if check:
			print(n // 2)
			continue
	for i in s:
		if i == '0':
			t0 += 1
		else:
			t1 += 1
	if t0 == t1:
		print(t1 - 1)
		continue
	print(min(t0, t1))


for _ in range(int(input())):
	n = int(input())
	s = input()
	e_array = []
	o_array = []
	for i in range(n):
		if i % 2 == 1:
			o_array.append(s[i])
		else:
			e_array.append(s[i])
	e_array = sorted(e_array)
	o_array = sorted(o_array, reverse=True)
	s1 = ''
	s2 = ''
	l1 = len(e_array)
	l2 = len(o_array)
	N = min(l1, l2)
	for i in range(N):
		s1 += e_array[i] + o_array[i]
		s2 += e_array[l1 - i - 1] + o_array[l2 - i - 1]
	if l1 > l2:
		s1 += e_array[-1]
		s2 += e_array[0]
	c1 = s1.count('01')
	c2 = s2.count('01')
	print(max(c1, c2))


n = int(input())
for _ in range(n):
	N = int(input())
	S = input()
	even = []
	odd = []
	for i in range(N):
		if i % 2:
			odd.append(S[i])
		else:
			even.append(S[i])
	if N % 2:
		st1 = ''
		odd1 = sorted(odd, reverse=True)
		even1 = sorted(even)
		for i in range(N // 2):
			st1 += even1[i]
			st1 += odd1[i]
		st1 += even1[-1]
		q1 = st1.count('01')
		st2 = ''
		odd2 = sorted(odd)
		even2 = sorted(even, reverse=True)
		for i in range(N // 2):
			st2 += even2[i]
			st2 += odd2[i]
		st2 += even2[-1]
		q2 = st2.count('01')
		ans = max(q1, q2)
		print(ans)
	else:
		st1 = ''
		odd1 = sorted(odd, reverse=True)
		even1 = sorted(even)
		for i in range(N // 2):
			st1 += even1[i]
			st1 += odd1[i]
		q1 = st1.count('01')
		st2 = ''
		odd2 = sorted(odd)
		even2 = sorted(even, reverse=True)
		for i in range(N // 2):
			st2 += even2[i]
			st2 += odd2[i]
		q2 = st2.count('01')
		ans = max(q1, q2)
		print(ans)


try:
	for _ in range(int(input())):
		n = int(input())
		st = input()
		(t1, t0) = (0, 0)
		n = len(st)
		flag1 = True
		if n % 2 == 0:
			for i in range(0, n - 1, 2):
				if st[i] != '0' or st[i + 1] != '1':
					flag1 = False
			if flag1:
				print(n // 2)
				continue
		for i in range(n):
			if st[i] == '1':
				t1 += 1
			if st[i] == '0':
				t0 += 1
		if t1 == t0:
			print(t1 - 1)
			continue
		print(min(t1, t0))
except:
	pass


def count01(arr):
	c = 0
	prev = arr[0]
	for idx in range(1, len(arr)):
		if prev is None:
			prev = arr[idx]
		if prev == 0:
			if arr[idx] == 1:
				c += 1
				prev = None
			else:
				prev = arr[idx]
		if prev == 1:
			prev = arr[idx]
	return c

def maxOcc(n, s):
	even_list = []
	odd_list = []
	even_entry = True
	for (idx, char) in enumerate(s):
		if even_entry is True:
			even_list.append(char)
			even_entry = False
		else:
			odd_list.append(char)
			even_entry = True
	c1 = 0
	even_list = sorted(even_list, reverse=True)
	odd_list = sorted(odd_list)
	joined_list = []
	for idx in range(n // 2 + 1):
		if idx < len(even_list):
			joined_list.append(even_list[idx])
		if idx < len(odd_list):
			joined_list.append(odd_list[idx])
	c1 = count01(joined_list)
	joined_list_2 = []
	even_list.reverse()
	odd_list.reverse()
	for idx in range(n // 2 + 1):
		if idx < len(even_list):
			joined_list_2.append(even_list[idx])
		if idx < len(odd_list):
			joined_list_2.append(odd_list[idx])
	c2 = count01(joined_list_2)
	return max(c1, c2)
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input()))
	print(maxOcc(n, s))


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

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

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		even1 = 0
		odd1 = 0
		even0 = 0
		odd0 = 0
		e1 = 0
		o1 = 0
		e0 = 0
		o0 = 0
		for i in range(n):
			if i & 1:
				if s[i] == '0':
					odd0 += 1
				if s[i] == '1':
					odd1 += 1
			else:
				if s[i] == '1':
					even1 += 1
				if s[i] == '0':
					even0 += 1
		e1 = even1
		o1 = odd1
		e0 = even0
		o0 = odd0
		s1 = ['0' for i in range(n)]
		s2 = ['0' for i in range(n)]
		i = 0
		j = 1
		while 1:
			if e0 > 0:
				s1[i] = '0'
				i += 2
				e0 -= 1
			elif e1 > 0:
				s1[i] = '1'
				i += 2
				e1 -= 1
			if o1 > 0:
				s1[j] = '1'
				j += 2
				o1 -= 1
			elif o0 > 0:
				s1[j] = '0'
				j += 2
				o0 -= 1
			if e0 == 0 and e1 == 0 and (o0 == 0) and (o1 == 0):
				break
		e1 = even1
		o1 = odd1
		e0 = even0
		o0 = odd0
		i = 0
		j = 1
		while 1:
			if e1 > 0:
				s2[i] = '1'
				i += 2
				e1 -= 1
			elif e0 > 0:
				s2[i] = '0'
				i += 2
				e0 -= 1
			if o0 > 0:
				s2[j] = '0'
				j += 2
				o0 -= 1
			elif o1 > 0:
				s2[j] = '1'
				j += 2
				o1 -= 1
			if e0 == 0 and e1 == 0 and (o0 == 0) and (o1 == 0):
				break
		s1 = ''.join(s1)
		s2 = ''.join(s2)
		count1 = s1.count('01')
		count2 = s2.count('01')
		print(max(count1, count2))
main()


tc = int(input())
while tc:
	length = int(input())
	string = input()
	even_index = [i for (j, i) in enumerate(string) if j % 2 == 0]
	odd_index = [i for (j, i) in enumerate(string) if j % 2 != 0]
	even_index.sort(reverse=True)
	odd_index.sort()
	new_string = ''
	for i in range(min(len(even_index), len(odd_index))):
		new_string += even_index[i]
		new_string += odd_index[i]
	if len(odd_index) > len(even_index):
		new_string += odd_index[-1]
	if len(odd_index) < len(even_index):
		new_string += even_index[-1]
	even_index.sort()
	odd_index.sort(reverse=True)
	new_string_2 = ''
	for i in range(min(len(even_index), len(odd_index))):
		new_string_2 += even_index[i]
		new_string_2 += odd_index[i]
	if len(odd_index) > len(even_index):
		new_string_2 += odd_index[-1]
	if len(odd_index) < len(even_index):
		new_string_2 += even_index[-1]
	pattern = '01'
	max_01 = 0
	max_02 = 0
	j = 1
	flag = 0
	for i in range(0, len(new_string) - 1):
		if pattern == new_string[i:i + 2]:
			max_01 += 1
	for i in range(0, len(new_string_2) - 1):
		if pattern == new_string_2[i:i + 2]:
			max_02 += 1
	print(max(max_01, max_02))
	tc -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	(o, e) = (Counter(s[1::2]), Counter(s[0::2]))
	A = e['0']
	B = o['0']
	C = e['1']
	D = o['1']
	t = 0
	while A and D:
		t += 1
		A -= 1
		D -= 1
	if not A:
		C -= 1
	if C == -1:
		C += 1
	while B and C:
		t += 1
		B -= 1
		C -= 1
	print(t)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	l = [0] * n
	(even, odd) = ([], [])
	for i in range(1, n + 1):
		if i % 2 == 0:
			even.append(s[i - 1])
		else:
			odd.append(s[i - 1])
	o1 = sorted(odd)
	e1 = sorted(even, reverse=True)
	(j, k) = (0, 0)
	for i in range(1, n + 1):
		if i % 2 == 0:
			l[i - 1] = e1[j]
			j += 1
		else:
			l[i - 1] = o1[k]
			k += 1
	st1 = ''.join(l)
	c1 = st1.count('01')
	e2 = sorted(even)
	o2 = sorted(odd, reverse=True)
	(j, k) = (0, 0)
	l1 = [0] * n
	for i in range(1, n + 1):
		if i % 2 == 0:
			l1[i - 1] = e2[j]
			j += 1
		else:
			l1[i - 1] = o2[k]
			k += 1
	st2 = ''.join(l1)
	c2 = st2.count('01')
	print(max(c1, c2))
	t -= 1


test = int(input())
for i in range(test):
	n = int(input())
	s = input()
	lst = list(s)
	count1 = lst.count('1')
	count0 = lst.count('0')
	eve1 = 0
	eve0 = 0
	odd1 = 0
	odd0 = 0
	for i in range(len(lst)):
		if i % 2 == 0:
			if lst[i] == '1':
				eve1 += 1
			else:
				eve0 += 1
		elif lst[i] == '1':
			odd1 += 1
		else:
			odd0 += 1
	lst1 = []
	lst2 = []
	tempeve0 = eve0
	tempeve1 = eve1
	tempodd0 = odd0
	tempodd1 = odd1
	while eve0 > 0 or eve1 > 0:
		if eve0 > 0:
			lst1.append('0')
			eve0 -= 1
		else:
			lst1.append('1')
			eve1 -= 1
	while odd0 > 0 or odd1 > 0:
		if odd1 > 0:
			lst2.append('1')
			odd1 -= 1
		else:
			lst2.append('0')
			odd0 -= 1
	lst3 = []
	cnt = 0
	cnt2 = 0
	for i in range(n):
		if i % 2 == 0:
			lst3.append(lst1[cnt])
			cnt += 1
		else:
			lst3.append(lst2[cnt2])
			cnt2 += 1
	ans1 = 0
	for i in range(len(lst3) - 1):
		if lst3[i] == '0' and lst3[i + 1] == '1':
			ans1 += 1
	eve0 = tempeve0
	eve1 = tempeve1
	odd0 = tempodd0
	odd1 = tempodd1
	lst4 = []
	lst5 = []
	while eve0 > 0 or eve1 > 0:
		if eve1 > 0:
			lst4.append('1')
			eve1 -= 1
		else:
			lst4.append('0')
			eve0 -= 1
	while odd0 > 0 or odd1 > 0:
		if odd0 > 0:
			lst5.append('0')
			odd0 -= 1
		else:
			lst5.append('1')
			odd1 -= 1
	lst6 = []
	cnt4 = 0
	cnt5 = 0
	for i in range(n):
		if i % 2 == 0:
			lst6.append(lst4[cnt4])
			cnt4 += 1
		else:
			lst6.append(lst5[cnt5])
			cnt5 += 1
	ans2 = 0
	for i in range(len(lst6) - 1):
		if lst6[i] == '0' and lst6[i + 1] == '1':
			ans2 += 1
	print(max(ans1, ans2))


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	x = list(s)
	a = []
	b = []
	for i in range(0, len(x)):
		if i % 2 == 0:
			a.append(x[i])
		else:
			b.append(x[i])
	a.sort()
	b.sort()
	c = []
	for i in b:
		c.append(i)
	d = []
	for i in a:
		d.append(i)
	c.reverse()
	d.reverse()
	for i in range(len(b)):
		a.insert(2 * i + 1, c[i])
	for i in range(len(d)):
		b.insert(2 * i, d[i])
	e = 0
	f = 0
	for i in range(1, len(a)):
		if a[i - 1] == '0' and a[i] == '1':
			e += 1
	for i in range(1, len(b)):
		if b[i - 1] == '0' and b[i] == '1':
			f += 1
	print(max(e, f))


def gt(N, B):
	cnt = 0
	i = 0
	while i < N:
		if i + 1 < N and B[i] == '0' and (B[i + 1] == '1'):
			cnt += 1
			i += 2
		else:
			i += 1
	return cnt
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(Even, Odd) = ([], [])
	for i in range(N):
		if i % 2:
			Even.append(S[i])
		else:
			Odd.append(S[i])
	Odd.sort()
	Even.sort(reverse=True)
	B = ''
	(i, j) = (0, 0)
	while i < len(Odd) or j < len(Even):
		if i < len(Odd):
			B += Odd[i]
			i += 1
		if j < len(Even):
			B += Even[j]
			j += 1
	Odd.sort(reverse=True)
	Even.sort()
	ans = gt(N, B)
	P = ''
	(i, j) = (0, 0)
	while i < len(Odd) or j < len(Even):
		if i < len(Odd):
			P += Odd[i]
			i += 1
		if j < len(Even):
			P += Even[j]
			j += 1
	ans = max(ans, gt(N, P))
	print(ans)


t = input()
t = int(t)
while t != 0:
	t = t - 1
	x = int(input())
	s = input()
	c1 = 0
	c0 = 0
	c1o = 0
	c0o = 0
	c1e = 0
	c0e = 0
	for i in range(0, len(s)):
		if s[i] == '1' and i % 2 == 0:
			c1 += 1
			c1e += 1
		elif s[i] == '0' and i % 2 == 1:
			c0 += 1
			c0e += 1
		if s[i] == '1' and i % 2 == 1:
			c1o += 1
			c1e += 1
		elif s[i] == '0' and i % 2 == 0:
			c0o += 1
			c0e += 1
	res = 0
	n = len(s)
	x1 = True
	x2 = True
	i = 0
	while i <= n - 2:
		if s[i] == '0' and s[i + 1] == '1':
			pass
		else:
			x1 = False
		if s[i] == '1' and s[i + 1] == '0':
			pass
		else:
			x2 == False
		i += 2
	if x1:
		try:
			if len(s) == 2 and s[0] == '1' and (s[1] == '0'):
				print(0)
				continue
			else:
				print(n // 2)
				continue
		except:
			pass
	elif x2:
		try:
			if s[n] == '1':
				print(n // 2)
				continue
		except:
			pass
	if c1e == c0e:
		res = c1e - 1
	elif c1e < c0e:
		res = c1e
	elif c1e > c0e:
		res = c0e
	print(res)


for i in range(int(input())):
	odd1s = 0
	even0s = 0
	odd0s = 0
	even1s = 0
	ln = int(input())
	rawlist = input()
	flag = True
	for i in range(ln):
		if flag:
			if int(rawlist[i]) == 0:
				even0s += 1
			else:
				even1s += 1
		elif int(rawlist[i]) == 1:
			odd1s += 1
		else:
			odd0s += 1
		flag = not flag
	mainlst = []
	m_even0s = even0s
	m_even1s = even1s
	m_odd0s = odd0s
	m_odd1s = odd1s
	for i in range(ln):
		if not i & 1:
			if even0s > 0:
				mainlst.append(0)
				even0s -= 1
			else:
				mainlst.append(1)
		elif odd1s > 0:
			mainlst.append(1)
			odd1s -= 1
		else:
			mainlst.append(0)
	count = 0
	i = 0
	flag = True
	while i < len(mainlst) - 1:
		if mainlst[i] == 0:
			if mainlst[i + 1] == 1:
				count += 1
				i += 1
		i += 1
	mainlst2 = []
	i = 0
	for i in range(ln):
		if not i & 1:
			if m_even1s > 0:
				mainlst2.append(1)
				m_even1s -= 1
			else:
				mainlst2.append(0)
		elif m_odd0s > 0:
			mainlst2.append(0)
			m_odd0s -= 1
		else:
			mainlst2.append(1)
	count2 = 0
	i = 0
	while i < len(mainlst2) - 1:
		if mainlst2[i] == 0:
			if mainlst2[i + 1] == 1:
				count2 += 1
				i += 1
		i += 1
	print(max(count2, count))


import math
import os
import random
import re
import sys

def gt(N, B):
	cnt = 0
	i = 0
	while i < N:
		if i + 1 < N and B[i] == '0' and (B[i + 1] == '1'):
			cnt += 1
			i += 2
		else:
			i += 1
	return cnt
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(Ev, Od) = ([], [])
	for i in range(N):
		if i % 2:
			Ev.append(S[i])
		else:
			Od.append(S[i])
	Od.sort()
	Ev.sort(reverse=True)
	B = ''
	(i, j) = (0, 0)
	while i < len(Od) or j < len(Ev):
		if i < len(Od):
			B += Od[i]
			i += 1
		if j < len(Ev):
			B += Ev[j]
			j += 1
	Od.sort(reverse=True)
	Ev.sort()
	ans = gt(N, B)
	P = ''
	(i, j) = (0, 0)
	while i < len(Od) or j < len(Ev):
		if i < len(Od):
			P += Od[i]
			i += 1
		if j < len(Ev):
			P += Ev[j]
			j += 1
	ans = max(ans, gt(N, P))
	print(ans)


def add(a, b):
	x = ''
	for i in range(len(a + b)):
		if i % 2 == 0:
			if len(a) != 0:
				x += str(a.pop())
		elif len(b) != 0:
			x += str(b.pop())
	return x

def sort_o(s, l):
	even = []
	for i in range(1, l, 2):
		even += [int(s[i])]
	odd = []
	for i in range(0, l, 2):
		odd += [int(s[i])]
	odd.sort(reverse=True)
	even.sort()
	c1 = add(odd, even)
	return c1

def sort_e(s, l):
	even = []
	for i in range(1, l, 2):
		even += [int(s[i])]
	odd = []
	for i in range(0, l, 2):
		odd += [int(s[i])]
	odd.sort()
	even.sort(reverse=True)
	c1 = add(odd, even)
	return c1
for i in range(int(input())):
	l = int(input())
	s = input()
	a = sort_e(s, l)
	b = sort_o(s, l)
	print(max(a.count('01'), b.count('01')))


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def check(s):
	return s.count('01')

def alternate(a, b):
	s = ''
	p = q = 0
	for i in range(n):
		if i % 2 == 0:
			s += a[p]
			p += 1
		else:
			s += b[q]
			q += 1
	return s
for _ in range(int(input())):
	n = int(input())
	s = input()
	even_index_count_0 = 0
	even_index_count_1 = 0
	odd_index_count_0 = 0
	odd_index_count_1 = 0
	for i in range(n):
		if i % 2 == 0:
			if s[i] == '1':
				even_index_count_1 += 1
			else:
				even_index_count_0 += 1
		elif s[i] == '1':
			odd_index_count_1 += 1
		else:
			odd_index_count_0 += 1
	even_elements_1_start = '1' * even_index_count_1 + '0' * even_index_count_0
	odd_element_1_start = '1' * odd_index_count_1 + '0' * odd_index_count_0
	even_elements_0_start = '0' * even_index_count_0 + '1' * even_index_count_1
	odd_element_0_start = '0' * odd_index_count_0 + '1' * odd_index_count_1
	s1 = alternate(even_elements_1_start, odd_element_0_start)
	s2 = alternate(even_elements_0_start, odd_element_1_start)
	ans = max(check(s1), check(s2))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	even = []
	odd = []
	for i in range(len(s)):
		if i % 2 == 0:
			even.append(s[i])
		else:
			odd.append(s[i])
	even.sort()
	odd.sort(reverse=True)
	new_str = ''
	j = 0
	k = 0
	for i in range(len(s)):
		if i % 2 == 0:
			new_str = new_str + even[j]
			j = j + 1
		else:
			new_str = new_str + odd[k]
			k = k + 1
	count1 = new_str.count('01')
	even.sort(reverse=True)
	odd.sort()
	new_str = ''
	j = 0
	k = 0
	for i in range(len(s)):
		if i % 2 == 0:
			new_str = new_str + even[j]
			j += 1
		else:
			new_str = new_str + odd[k]
			k += 1
	count2 = new_str.count('01')
	print(max(count1, count2))


for _ in range(int(input())):
	N = int(input())
	S = input()
	(count0, count1) = (0, 0)
	for i in range(N):
		if S[i] == '0':
			count0 += 1
		elif S[i] == '1':
			count1 += 1
	(start, end, i, ex1, ex2) = (0, 0, 0, True, True)
	if len(S) % 2 == 0:
		end = len(S)
	elif len(S) % 2 == 1:
		end = len(S) - 1
	while i < end:
		if not (S[i] == '0' and S[i + 1] == '1'):
			ex1 = False
		if not (S[i] == '1' and S[i + 1] == '0'):
			ex2 = False
		i += 2
	if ex1 and len(S) % 2 == 0:
		print(len(S) // 2)
		continue
	elif ex1 and len(S) % 2 == 1:
		print((len(S) - 1) // 2)
		continue
	elif ex2 and len(S) % 2 == 0:
		print(len(S) // 2 - 1)
		continue
	elif ex2 and len(S) % 2 == 1:
		print((len(S) - 1) // 2)
		continue
	if count0 == count1:
		print(count1 - 1)
	elif count0 < count1:
		print(count0)
	elif count0 > count1:
		print(count1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = sorted([s[i] for i in range(0, len(s), 2)])
	y = sorted([s[i] for i in range(1, len(s), 2)], reverse=True)
	l = ''
	a = 0
	b = 0
	for i in range(len(s)):
		if i % 2 == 0:
			l += x[a]
			a += 1
		else:
			l += y[b]
			b += 1
	x.reverse()
	y.reverse()
	m = ''
	a = 0
	b = 0
	for i in range(len(s)):
		if i % 2 == 0:
			m += x[a]
			a += 1
		else:
			m += y[b]
			b += 1
	print(max(l.count('01'), m.count('01')))


def countZeroOne(arr, n):
	ans = 0
	for i in range(n):
		if arr[i] == 0 and arr[i + 1] == 1:
			ans += 1
	return ans

def mergeTwoList(arr1, arr2, n):
	if n & 1:
		arr = [x for y in zip(arr1, arr2) for x in y] + [arr1[-1]]
		return arr
	else:
		arr = [x for y in zip(arr1, arr2) for x in y]
		return arr

def sortSmallerToGreater(arr):
	arr.sort()
	return arr

def sortGreaterToSmaller(arr):
	return sorted(arr, reverse=True)

def seprateIntoOddEven(arr, n):
	oddList = []
	evenList = []
	for i in range(n):
		if i + 1 & 1:
			oddList += [arr[i]]
		else:
			evenList += [arr[i]]
	return (oddList, evenList)
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input()]
	(oddList, evenList) = seprateIntoOddEven(arr, n)
	case1OddList = sortSmallerToGreater(oddList)
	case1EvenList = sortGreaterToSmaller(evenList)
	ans1 = countZeroOne(mergeTwoList(case1OddList, case1EvenList, n), n - 1)
	case2OddList = sortGreaterToSmaller(oddList)
	case2EvenList = sortSmallerToGreater(evenList)
	ans2 = countZeroOne(mergeTwoList(case2OddList, case2EvenList, n), n - 1)
	ans = max(ans1, ans2)
	print(ans)


def solve():
	n = int(input())
	s = input()
	c1 = 0
	c2 = 0
	c3 = 0
	c4 = 0
	c5 = 0
	c6 = 0
	for i in range(len(s)):
		if s[i] == '1' and i % 2 == 0:
			c1 += 1
			c5 += 1
		elif s[i] == '0' and i % 2 == 1:
			c2 += 1
			c6 += 1
		if s[i] == '1' and i % 2 == 1:
			c3 += 1
			c5 += 1
		elif s[i] == '0' and i % 2 == 0:
			c4 += 1
			c6 += 1
	ans = 0
	k = len(s)
	if k % 2 == 1:
		k -= 1
	v1 = True
	v2 = True
	for i in range(0, k - 1):
		if s[i] == '0' and s[i + 1] == '1':
			continue
		else:
			v1 = False
		if s[i] == '1' and s[i + 1] == '0':
			continue
		else:
			v2 = False
	if v1 == True:
		print(k // 2)
		return
	elif v2 == True:
		if s[k - 1] == '1':
			print(k // 2)
			return
	if c5 == c6:
		ans = c5 - 1
	elif c5 < c6:
		ans = c5
	elif c5 > c6:
		ans = c6
	print(ans)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	(odd_0, odd_1, even_0, even_1) = (0, 0, 0, 0)
	for j in range(len(a)):
		if j % 2 == 0:
			if a[j] == '0':
				even_0 += 1
			else:
				even_1 += 1
		elif a[j] == '0':
			odd_0 += 1
		else:
			odd_1 += 1
	if (min([odd_1, even_0]) + min(odd_0, even_1)) * 2 == n and min(odd_0, even_1) != 0:
		print(min([odd_1, even_0]) + min(odd_0, even_1) - 1)
	else:
		print(min([odd_1, even_0]) + min(odd_0, even_1))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lsteven = []
	lstodd = []
	for i in range(0, len(s), 2):
		lsteven.append(s[i])
	for i in range(1, len(s), 2):
		lstodd.append(s[i])
	lsteven.sort()
	lstodd.sort(reverse=True)
	s1 = ''
	(indxeven, indxodd) = (0, 0)
	for i in range(n):
		try:
			if i % 2 == 0:
				s1 += lsteven[indxeven]
				indxeven += 1
			else:
				s1 += lstodd[indxodd]
				indxodd += 1
		except:
			break
	lsteven.sort(reverse=True)
	lstodd.sort()
	s2 = ''
	(indxeven, indxodd) = (0, 0)
	for i in range(n):
		try:
			if i % 2 == 0:
				s2 += lsteven[indxeven]
				indxeven += 1
			else:
				s2 += lstodd[indxodd]
				indxodd += 1
		except:
			break
	(a, b) = (0, 0)
	for i in range(n - 1):
		try:
			if s1[i] == '0' and s1[i + 1] == '1':
				a += 1
			if s2[i] == '0' and s2[i + 1] == '1':
				b += 1
		except:
			continue
	print(max(a, b))


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a1 = 0
	b1 = 0
	a2 = 0
	b2 = 0
	for i in range(n):
		if i % 2 == 0:
			if s[i] == '0':
				a1 += 1
			else:
				b1 += 1
		elif s[i] == '0':
			a2 += 1
		else:
			b2 += 1
	aa1 = a1 * '0' + b1 * '1'
	aa2 = min(a1, b2) * '1' + a2 * '0' + (b2 - min(a1, b2)) * '1'
	i1 = 0
	i2 = 0
	ans = ''
	for i in range(n):
		if i % 2 == 0:
			ans += aa1[i1]
			i1 += 1
		else:
			ans += aa2[i2]
			i2 += 1
	final_ans1 = ans.count('01')
	print(final_ans1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	odd1 = ''
	even1 = ''
	odd2 = ''
	even2 = ''
	for i in range(n):
		if i % 2 == 0:
			odd1 += s[i]
			odd2 += s[i]
		else:
			even1 += s[i]
			even2 += s[i]
	odd1 = ''.join(sorted(odd1))
	odd2 = ''.join(sorted(odd2, reverse=True))
	even1 = ''.join(sorted(even1, reverse=True))
	even2 = ''.join(sorted(even2))
	str1 = ''
	str2 = ''
	temp = max(len(odd1), len(even1))
	j = 0
	for i in range(n):
		if i % 2 == 0:
			str1 += odd1[j]
			str2 += odd2[j]
		else:
			str1 += even1[j]
			str2 += even2[j]
			j += 1
	print(max(str1.count('01'), str2.count('01')))


for _ in range(int(input())):
	n = int(input())
	s = input()
	eZero = 0
	eOne = 0
	oZero = 0
	oOne = 0
	for i in range(n):
		if i % 2 and s[i] == '1':
			oOne += 1
		elif i % 2 and s[i] == '0':
			oZero += 1
		elif s[i] == '1':
			eOne += 1
		elif s[i] == '0':
			eZero += 1
	res = min(oOne, eZero)
	if eZero - oOne or eOne - oZero:
		res += min(eOne, oZero)
	elif min(eOne, oZero):
		res += min(eOne, oZero) - 1
	print(res)


test = int(input())
while test:
	n = int(input())
	s = input()
	i = c = 0
	even_one = even_zero = odd_one = odd_zero = 0
	while i < n:
		if s[i] == '0':
			if i % 2 == 0:
				even_zero += 1
			else:
				odd_zero += 1
		elif i % 2 == 0:
			even_one += 1
		else:
			odd_one += 1
		i += 1
	stop = 0
	if even_zero > odd_one:
		stop = odd_one
		even_zero -= odd_one
		odd_one = 0
	else:
		stop = even_zero
		odd_one -= even_zero
		even_zero = 0
	for i in range(stop):
		c += 1
	if even_zero:
		even_zero -= 1
	else:
		even_one -= 1
	if odd_zero > even_one:
		stop = even_one
		odd_zero -= even_one
		even_one = 0
	else:
		stop = odd_zero
		even_one -= odd_zero
		odd_zero = 0
	for i in range(stop):
		c += 1
	print(c)
	test -= 1


def m(a, b):
	i = 0
	j = 0
	c = []
	while i < len(a) and j < len(b):
		c.append(a[i])
		c.append(b[j])
		i += 1
		j += 1
	while i < len(a):
		c.append(a[i])
		i += 1
	while j < len(b):
		c.append(b[j])
		j += 1
	return c

def fun(n, s):
	a = []
	b = []
	for i in range(n):
		if i % 2 == 0:
			a.append(s[i])
		else:
			b.append(s[i])
	a.sort(reverse=True)
	b.sort()
	c = m(a, b)
	c1 = 0
	for i in range(len(c) - 1):
		if c[i] == '0' and c[i + 1] == '1':
			c1 += 1
	a.sort()
	b.sort(reverse=True)
	c = m(a, b)
	c2 = 0
	for i in range(len(c) - 1):
		if c[i] == '0' and c[i + 1] == '1':
			c2 += 1
	print(max(c1, c2))
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	fun(n, s)


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	even = []
	odd = []
	for i in input():
		if count % 2:
			odd.append(int(i))
		else:
			even.append(int(i))
		count += 1

	def calc(even, odd, n):
		merge = []
		(a, b) = (0, 0)
		for i in range(n):
			if i % 2:
				merge.append(odd[a])
				a += 1
			else:
				merge.append(even[b])
				b += 1
		count = 0
		for i in range(n):
			if merge[i] == 0 and i + 1 < n and (merge[i + 1] == 1):
				count += 1
		return count
	print(max(calc(sorted(even), sorted(odd, reverse=True), n), calc(sorted(even, reverse=True), sorted(odd), n)))


for test in range(int(input())):
	n = int(input())
	s = input()
	odd = []
	even = []
	zero = []
	c = 1
	ans = 0
	for i in range(n):
		if i % 2 == 1:
			odd.append(s[i])
		else:
			even.append(s[i])
	eo = even.count('1')
	ez = even.count('0')
	oo = odd.count('1')
	oz = odd.count('0')
	mi = min(ez, oo)
	ez -= mi
	oo -= mi
	if ez > 0:
		ez -= c
	else:
		eo -= c
	print(mi + max(ans, min(eo, oz)))


for _ in range(int(input())):
	N = int(input())
	S = input()[:N]
	(ct1, ct0, k) = (0, 0, 0)
	s = ''
	for i in range(N):
		if S[i] == '1':
			ct1 += 1
		else:
			ct0 += 1
	if ct1 < ct0:
		print(ct1)
		continue
	elif ct1 > ct0:
		print(ct0)
		continue
	for i in range(1, N + 1):
		if i % 2 == 1:
			s += '0'
		else:
			s += '1'
	for j in range(N):
		if S[j] != s[j]:
			k = 1
			break
	if k == 0:
		print(ct0)
	else:
		print(ct0 - 1)


import os, sys, math, cmath, time, collections
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace
from math import ceil, floor, log, log2, sqrt, gcd, factorial, pow, pi
from bisect import bisect_left, bisect_right

def input_as_array():
	return list(map(int, input().split()))
start_time = time.time()
p = 31
m = 10 ** 9 + 9

def compute_hash(s):
	n = len(s)
	power_mod = [1]
	for i in range(n):
		power_mod.append(power_mod[-1] * p % m)
	hash_values = [0] * (n + 1)
	for i in range(n):
		hash_values[i + 1] = (hash_values[i] + (ord(s[i]) - ord('a') + 1) * power_mod[i]) % m
	return hash_values

def count_occurences(text, pattern):
	text_length = len(text)
	pattern_length = len(pattern)
	power_mod = [1]
	for i in range(text_length):
		power_mod.append(power_mod[-1] * p % m)
	hash_values = [0] * (text_length + 1)
	for i in range(text_length):
		hash_values[i + 1] = (hash_values[i] + (ord(text[i]) - ord('a') + 1) * power_mod[i]) % m
	pattern_hash = 0
	for i in range(pattern_length):
		pattern_hash += (ord(pattern[i]) - ord('a') + 1) * power_mod[i] % m
	occurences = []
	i = 0
	while i + pattern_length - 1 < text_length:
		field_hash = (hash_values[i + pattern_length] - hash_values[i] + m) % m
		if field_hash == pattern_hash * power_mod[i] % m:
			occurences.append(i)
		i += 1
	return len(occurences)

def main():
	n = int(input())
	s = input()
	even_map = defaultdict(int)
	odd_map = defaultdict(int)
	for (i, c) in enumerate(s):
		if i % 2 == 0:
			even_map[c] += 1
		elif i % 2 != 0:
			odd_map[c] += 1
	ans = ''
	switch = False
	for i in range(n):
		if i % 2 == 0:
			if switch == False:
				if even_map['0'] > 0:
					ans += '0'
					even_map['0'] -= 1
					switch = False
				else:
					ans += '1'
					switch = True
			elif even_map['1'] > 0:
				ans += '1'
				even_map['1'] -= 1
			else:
				ans += '0'
		elif i % 2 != 0:
			if switch == False:
				if odd_map['1'] > 0:
					ans += '1'
					odd_map['1'] -= 1
					switch = False
				else:
					ans += '0'
					switch = True
			elif switch == True:
				if odd_map['0'] > 0:
					ans += '0'
					odd_map['0'] -= 1
				else:
					ans += '1'
	op = count_occurences(ans, '01')
	print(op)
if os.path.exists('data.in'):
	sys.stdin = open('data.in', 'r')
	sys.stdout = open('data.out', 'w')
testcases = int(input())
for i in range(testcases):
	main()
if os.path.exists('data.in'):
	print(f'Time Elapsed: {time.time() - start_time} seconds')
	sys.stdout.close()


for _ in range(int(input())):
	m = int(input())
	l = input()
	a = 0
	b = 0
	for j in range(m):
		if j % 2 == 0 and l[j] == '0':
			a += 1
		if j % 2 == 1 and l[j] == '1':
			b += 1
	if m % 2 == 1:
		if a <= b:
			print(a + m // 2 - b)
		else:
			print(b + m - m // 2 - a)
	elif a < b or (a == b and a == m // 2):
		print(a + m // 2 - b)
	elif a == b:
		print(a + m // 2 - b - 1)
	else:
		print(b + m // 2 - a)


def odd(l, lc, c):
	if l[0] > 0 and l[3] > 0:
		l[0] -= 1
		l[3] -= 1
		c[0] += 1
		lc[0] += 2
		return True
	else:
		lc[0] += 1
		return False

def even(l, lc, c):
	if l[1] > 0 and l[2] > 0:
		l[1] -= 1
		l[2] -= 1
		c[0] += 1
		lc[0] += 2
		return True
	else:
		lc[0] += 1
		return False
for _ in range(int(input())):
	n: int = int(input())
	s = input()
	l = [0, 0, 0, 0]
	for i in range(1, n + 1):
		if i % 2 == 0:
			if s[i - 1] == '1':
				l[3] += 1
			else:
				l[2] += 1
		elif s[i - 1] == '1':
			l[1] += 1
		else:
			l[0] += 1
	t = 'o'
	c = [0]
	lc = [0]
	while lc[0] < n - 1:
		if t == 'o':
			if not odd(l, lc, c):
				t = 'e'
		elif t == 'e':
			if not even(l, lc, c):
				t = 'o'
	print(c[0])


t = int(input())
for i in range(t):
	l = input()
	ele = input()
	a = []
	for i in range(0, len(ele), 2):
		a += ele[i]
	a.sort()
	b = []
	for i in range(1, len(ele), 2):
		b += ele[i]
	b.sort(reverse=True)
	e = []
	j = 0
	k = 0
	for i in range(len(ele)):
		if i % 2 == 0:
			e += a[k]
			k += 1
		else:
			e += b[j]
			j += 1
	e = ' '.join(e)
	a = []
	for i in range(0, len(ele), 2):
		a += ele[i]
	a.sort(reverse=True)
	b = []
	for i in range(1, len(ele), 2):
		b += ele[i]
	b.sort()
	j = 0
	k = 0
	g = []
	for i in range(len(ele)):
		if i % 2 == 0:
			g += a[k]
			k += 1
		else:
			g += b[j]
			j += 1
	g = ' '.join(g)
	print(max(g.count('0 1'), e.count('0 1')))


for _ in range(int(input())):
	(n, s) = (int(input()), input())
	(a, b, x) = (s.count('0'), s.count('1'), s[0])
	if n % 2 == 0 and a == n // 2 and (b == n // 2):
		ans = True
		for i in range(1, n):
			if s[i] != x:
				x = s[i]
			else:
				ans = False
				break
		if s[0] == '0' and ans == True:
			print(n // 2)
		else:
			print(n // 2 - 1)
	else:
		print(n - max(a, b))


T = int(input())
for i in range(T):
	n = int(input())
	s = str(input())
	oddzero = 0
	oddone = 0
	evenzero = 0
	evenone = 0
	for b in range(n):
		if b % 2 != 0:
			if s[n - b - 1] == '0':
				evenzero += 1
			else:
				evenone += 1
		elif s[n - b - 1] == '0':
			oddzero += 1
		else:
			oddone += 1
	st = 0
	if True:
		st += min(oddzero, evenone)
		st += min(oddone, evenzero)
	if n % 2 == 0:
		if evenone == 0 or oddzero == 0:
			pass
		elif st == n // 2:
			st -= 1
	print(st)