You are given a binary string S of length N. You can perform the following operation on S:

Pick any set of indices such that no two picked indices are adjacent.
Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).

For example, consider the string S = 1101101.  
If we pick the indices \{1,3,6\}, then after flipping the values at picked indices, we will get  \underline{1}1\underline{0}11\underline{0}1 \rightarrow 0111111.  
Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.

Find the minimum number of operations required to convert all the characters of S to 0.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the length of the binary string S.
- The second line of each test case contains a binary string S of length N.

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

For each test case, output the minimum number of operations required to convert all the characters of S to 0.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$

----- Sample Input 1 ------ 
3
6
101001
5
00000
3
111

----- Sample Output 1 ------ 
1
0
2

----- explanation 1 ------ 
Test Case $1$: Pick the set of indices $\{1, 3, 6\}$. On flipping the values at these indices, the string becomes $000000$.

Test Case $2$: The string already has all characters equal to $0$.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	pairs = s.count('11')
	if '1' in s:
		if pairs > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


n = int(input())
for i in range(n):
	a = int(input())
	s = input()
	com = s.count('11')
	if '1' in s:
		if com > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count('1') < 1:
		print(0)
	else:
		k = 0
		for i in range(0, n - 1):
			if s[i] == '1' and s[i + 1] == '1':
				k = 2
				break
			else:
				continue
		if k == 0:
			print(1)
		else:
			print(k)


for i in range(int(input())):
	n = int(input())
	s = input()
	p = s.count('11')
	if '1' in s:
		if p > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


n = int(input())
for i in range(n):
	k = int(input())
	k1 = input()
	s = k1.count('11')
	if '1' in k1:
		if s > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


n = int(input())
for i in range(n):
	x = int(input())
	a = input()
	p = a.count('1')
	c = 0
	for i in range(len(a) - 1):
		if a[i] == '1' and a[i + 1] == '1':
			c += 1
	if p == 0:
		print(0)
	elif c == 0:
		print(1)
	else:
		print(2)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	pair = s.count('11')
	if '1' in s:
		if pair > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


for t in range(int(input())):
	n = int(input())
	s = input()
	c = s.count('11')
	if '1' in s:
		if c > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	if '1' not in st:
		print(0)
	elif '11' in st:
		print(2)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = s.count('11')
	if '1' in s:
		if p > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	cnt = 0
	maxi = 0
	zero = 0
	for i in range(len(s)):
		if s[i] == '1':
			cnt += 1
		else:
			zero += 1
			maxi = max(maxi, cnt)
			cnt = 0
	if cnt > 0:
		maxi = max(maxi, cnt)
	if maxi >= 2:
		print(2)
	elif maxi == 1:
		print(1)
	else:
		print(0)


for i in range(int(input())):
	n = int(input())
	s = input()
	if s.count('1') == 0:
		print(0)
	else:
		flag = 0
		for i in range(0, n - 1):
			if s[i] == '1' and s[i + 1] == '1':
				print(2)
				break
		else:
			print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count_1 = 0
	adjacent = False
	for i in range(n):
		if s[i] == '1':
			count_1 += 1
		if i < n - 1:
			if s[i] == s[i + 1] and s[i] == '1':
				adjacent = True
				break
	if adjacent:
		print(2)
	elif count_1 > 0:
		print(1)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	for i in range(1, len(s)):
		if s[i - 1] == '1' and s[i] == '1':
			c = c + 1
	if '1' in s and c == 0:
		print(1)
	elif c > 0:
		print(2)
	else:
		print(0)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		if s[i] == '1' and s[i + 1] == '1':
			count += 1
	if '1' in s and count == 0:
		print(1)
	elif count >= 1:
		print(2)
	else:
		print(0)


for i in range(int(input())):
	a = int(input())
	s = input()
	if a == s.count('0'):
		print(0)
	else:
		y = False
		for i in range(a - 1):
			if s[i] == '1' and s[i + 1] == '1':
				y = True
				break
		if y:
			print(2)
		else:
			print(1)


for i in range(int(input())):
	y = int(input())
	z = input()
	c1 = 0
	for j in range(y - 1):
		if z[j] == '1' and z[j + 1] == '1':
			c1 += 1
	f = z.count('0')
	if f == y:
		print(0)
	elif c1 > 0:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	x = int(input())
	lst = list(map(int, input()))
	ans = 0
	prathu = 0
	y = 0
	for i in range(x):
		if lst[i] == 1:
			ans += 1
			if ans > 0:
				if prathu < ans:
					prathu = ans
		else:
			ans = 0
	if prathu == 1:
		print(1)
	elif prathu == 0:
		print(0)
	else:
		print(2)


for i in range(int(input())):
	l = int(input())
	s = input()
	pairs = s.count('11')
	if '1' in s:
		if pairs > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


for i in range(int(input())):
	n = int(input())
	x = input()
	res = x.count('11')
	if '1' in x:
		if res > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


for _ in range(int(input())):
	x = int(input())
	a = input()[:x]
	y = a.count('11')
	if '1' in a:
		if y > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


t = int(input())
for test in range(0, t):
	n = int(input())
	string = input()
	count = 0
	one_one = string.count('11')
	one = string.count('1')
	if n == string.count('0'):
		print('0')
	elif one_one == 0:
		print('1')
	else:
		print('2')


t = int(input())
for _ in range(t):
	n = int(input())
	l = input()
	op = l.count('11')
	if '1' in l:
		if op > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


for i in range(int(input())):
	a = int(input())
	b = input()
	if b.count('0') == len(b):
		print(0)
	elif b.count('11') > 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = b.count('11')
	if '1' in b:
		if c > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')


cases = int(input())
for _ in range(cases):
	n = int(input())
	s = input()
	cnt = s.count('11')
	if '1' in s:
		if cnt > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	flag = 0
	for i in range(1, n):
		if s[i - 1] == '1' and s[i] == '1':
			count += 1
	if '1' not in s:
		print(0)
	elif count == 0:
		print(1)
	else:
		print(2)


test = int(input())
for i in range(test):
	n = int(input())
	s = input()
	if s.count('1') == 0:
		print(0)
	elif s.count('11') >= 1:
		print(2)
	else:
		print(1)


for i in range(int(input())):
	N = int(input())
	S = input()[:N]
	c = S.count('1')
	if c == 0:
		print(0)
	else:
		l = []
		x = 0
		for j in range(N):
			if S[j] == '1':
				l.append(j)
		for j in range(c - 1):
			if l[j + 1] - l[j] == 1:
				x += 1
				print(2)
				break
		if x == 0:
			print(1)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	m = '1'
	x = s.count('11')
	if m in s:
		if x > 0:
			print('2')
		else:
			print('1')
	else:
		print('0')
	t -= 1


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


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	if S.count('1') == 0:
		print('0')
	else:
		c = 0
		for j in range(N - 1):
			if S[j] == '1' and S[j + 1] == '1':
				c += 1
				break
		if c == 0:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	x = int(input())
	y = str(input())
	if y.count('1') == 0:
		print(0)
	else:
		pre = 0
		d = 0
		for val in y:
			if val == '1':
				pre += 1
			else:
				pre = 0
			if pre > 1:
				d = 1
		if d == 0:
			print(1)
		else:
			print(2)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	f = 0
	list1 = list(s)
	if '1' not in list1:
		print(0)
	else:
		for i in range(0, len(s) - 1):
			if list1[i] == '1' and list1[i + 1] == '1':
				f = -1
				break
		if f == 0:
			print(1)
		else:
			print(2)
	t = t - 1


for _ in range(int(input())):
	length = int(input())
	inputstr = input()
	flag = True
	countz = inputstr.count('0')
	if countz == length:
		print(0)
	else:
		for i in range(length - 1):
			if inputstr[i] == '1' and inputstr[i + 1] == '1':
				flag = False
				break
		if flag:
			print(1)
		else:
			print(2)


for t in range(int(input())):
	n = int(input())
	s = input()
	_0 = s.count('0')
	if _0 == n:
		print(0)
	else:
		Flag = True
		for i in range(1, n):
			if s[i - 1] == '1' and s[i] == '1':
				Flag = False
				break
		if Flag:
			print(1)
		else:
			print(2)


tc = int(input())
for i in range(tc):
	k = int(input())
	s = input()
	ans = 0
	if s == '0' * len(s):
		print(ans)
	else:
		i = 0
		ans += 1
		while i < len(s):
			if s[i] == '1':
				a = s[0:i]
				s = a + '0' + s[i + 1:len(s)]
				i += 2
			else:
				i += 1
			if i >= len(s) and s != '0' * len(s):
				i = 0
				ans += 1
			if s == '0' * k:
				print(ans)
				break


t = int(input())
for _ in range(t):
	l = int(input())
	s = str(input())
	r = str(s)
	if s.count('1') > 0:
		if s.count('11') > 0:
			print(2)
		else:
			print(1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = list(s)
	l = []
	for i in s:
		if i == '1':
			l.append(s1.index(i) + 1)
			s1[s1.index(i)] = 5
	if len(l) == 0:
		print(0)
	else:
		c = 0
		for i in range(len(l) - 1):
			if abs(l[i] - l[i + 1]) > 1:
				continue
			else:
				print(2)
				c += 1
				break
		if c == 0:
			print(1)


import re
for i in range(int(input())):
	n = int(input())
	s = input()
	r = s.count('1')
	res = len(re.findall('11', s))
	if r == 0:
		print('0')
	elif res == 0:
		print('1')
	else:
		print('2')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if '11' in s:
		print(2)
	elif '1' in s:
		print(1)
	else:
		print(0)


from math import *
for _ in range(int(input())):
	n = int(input())
	s = input()
	if '11' in s:
		print('2')
	elif '1' in s:
		print('1')
	else:
		print('0')


t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	if str(1) not in s:
		print(0)
		continue
	arr = []
	for j in range(n):
		if s[j] == '1':
			arr.append(j + 1)
	flag = 1
	for k in range(len(arr) - 1):
		if arr[k + 1] - arr[k] < 2:
			flag = 0
		else:
			continue
	if flag == 1:
		print(1)
	else:
		print(2)


for testcase in range(int(input())):
	number = int(input())
	string = input()
	if '11' in string:
		print('2')
	elif '1' in string:
		print('1')
	else:
		print('0')