Chef has a binary string S of size N. Chef can perform the following operation on the string:
Select any substring of size 3 and reverse it.

Find the minimum *distance* between any two 1s Chef can achieve, by applying the above operation any (possibly zero) number of times.

Note:
The *distance* between two characters S_{i} and S_{j} is defined as abs(i-j).
It is guaranteed that the string contains at least two occurrences of 1.
A substring is obtained by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the string.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of characters in the string.
- The next line contains a binary string of length N.

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

For each test case, output on a new line, the minimum distance between any two 1s Chef can achieve, by applying the above operation any (possibly zero) number of times.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$S_{i}$ contains $0$ and $1$ only.
- It is guaranteed that $S$ contains at least two occurrences of $1$.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
11
3
101
7
0100101

----- Sample Output 1 ------ 
1
2
1
----- explanation 1 ------ 
Test case $1$: There are only two $1$s in the string. The distance between the $1$s is $2-1 = 1$.

Test case $2$: The distance between the given $1$s is $3-1 = 2$. It can be shown that we cannot achieve a distance smaller than $2$ by applying any number of operations.

Test case $3$: Chef can perform the following operation:
- Select the substring $S[2,4] = 100$ and reverse it. Thus, the string becomes $S = 0001101$. The minimum distance between the $1$s in the string is $5-4 = 1$. 

It can be shown that we cannot achieve a distance smaller than $1$ by applying any number of operations.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc


Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	(ne, no) = (0, 0)
	s1 = s[0::2]
	s2 = s[1::2]
	if '1' in s1 and '1' in s2:
		print(1)
	else:
		print(2)


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	(ne, no) = (0, 0)
	for i in range(n):
		if i % 2 == 1 and s[i] == '1':
			no = no + 1
		elif i % 2 == 0 and s[i] == '1':
			ne = ne + 1
	if ne > 0 and no > 0:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = input()
	(a0, a1) = (0, 0)
	for i in range(n):
		if i % 2:
			a1 = 1 if a[i] == '1' else a1
		else:
			a0 = 1 if a[i] == '1' else a0
	if a0 and a1:
		print(1)
	else:
		print(2)


from collections import Counter
from math import gcd

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	S = input()
	na = True
	if '11' in S:
		print(1)
		continue
	ok = N - S[::-1].find('1')
	s = S.find('1')
	S = S[s:ok]
	arr = []
	clen = 0
	for i in range(len(S)):
		if S[i] == '0':
			clen += 1
		else:
			if clen != 0:
				arr.append(clen)
			clen = 0
	for i in arr:
		if i % 2 == 0:
			print(1)
			na = False
			break
	if na:
		print(2)


for tc in range(int(input())):
	n = int(input())
	s = input()
	(even, odd, ans) = (0, 0, 0)
	for i in range(len(s)):
		if s[i] == '1':
			if i % 2 == 0:
				even = 1
			else:
				odd = 1
	if even == 1 and odd == 1:
		ans = 1
	elif even == 1 or odd == 1:
		ans = 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	odd = 0
	eve = 0
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				eve += 1
			else:
				odd += 1
	if eve > 0 and odd > 0:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	b = input()
	(c1, c2) = (0, 0)
	for i in range(n):
		if b[i] == '1':
			if i % 2 == 0:
				c1 += 1
			else:
				c2 += 1
	if c1 > 0 and c2 > 0:
		print(1)
	else:
		print(2)


vojj = int(input())
for vishnesh in range(vojj):
	n = int(input())
	arr = input()
	o = []
	ce = 0
	co = 0
	ans = 2
	for i in range(n):
		if arr[i] == '1':
			if i % 2 == 1:
				co = co + 1
			else:
				ce = ce + 1
		if co >= 1 and ce >= 1:
			ans = 1
			break
	print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	size = len(s)
	itr = 0
	while itr < size:
		elem = s[itr]
		s_itr = itr
		chk = False
		upd = False
		if elem == '1':
			for i in range(itr + 1, size):
				if s[i] == '1':
					itr = i
					upd = True
					if (i - s_itr) % 2 != 0:
						print(1)
						chk = True
						break
			if chk == True:
				break
		if upd == False:
			itr += 1
	if chk != True:
		print(2)
	t -= 1


t = int(input())
for y in range(t):
	n = int(input())
	a = str(input())
	o = 0
	e = 0
	for x in range(n):
		if a[x] == '1':
			if x % 2 == 0:
				e += 1
			else:
				o += 1
	if o > 0 and e > 0:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	l = int(input())
	s = input()
	x = []
	for i in range(l):
		if s[i] == '1':
			x.append(i)
	isEven = False
	for i in range(1, len(x)):
		if (x[i] - x[i - 1]) % 2 == 1:
			isEven = True
	if isEven:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	N = int(input())
	instr = input()
	even_str = instr[::2]
	odd_str = instr[1::2]
	if even_str.count('1') >= 1 and odd_str.count('1') >= 1:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	N = int(input())
	Str = input()
	(one, zero) = (0, 0)
	for i in range(len(Str)):
		if Str[i] == '1':
			if i % 2 == 0:
				one += 1
			else:
				zero += 1
	print(1 if one and zero else 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	o = 0
	e = 0
	for i in range(n):
		if s[i] == '1':
			if (i + 1) % 2 == 0:
				e = 1
			else:
				o = 1
	print(1 if e and o else 2)


for _ in range(int(input())):
	n = int(input())
	num = input()
	odd = even = 0
	for i in range(n):
		if num[i] == '1':
			if i % 2:
				odd = 1
			else:
				even = 1
	print(1 if odd and even else 2)


t = int(input())
for i in range(t):
	a = int(input())
	l = input()
	u = 0
	v = 0
	for i in range(len(l)):
		if l[i] == '1' and i % 2 == 0:
			u += 1
		elif l[i] == '1' and i % 2 != 0:
			v += 1
	print(1) if u * v else print(2)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	E = 0
	O = 0
	for i in range(N):
		if S[i] == '1':
			if i % 2 == 0:
				E += 1
			else:
				O += 1
	if E > 0 and O > 0:
		print('1')
	else:
		print('2')


t = int(input())
s = ''
for _ in range(t):
	n = int(input())
	s = input()
	has_even = False
	has_odd = False
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				has_even = True
			else:
				has_odd = True
	if has_even and has_odd:
		print(1)
	else:
		print(2)


t = int(input())
for k in range(t):
	n = int(input())
	s = input()
	l = list((s[i:i + 1] for i in range(n)))
	flag_even = flag_odd = 0
	for i in range(n):
		if l[i] == '1':
			if i % 2 == 0:
				flag_even = 1
			else:
				flag_odd = 1
	if flag_even == 1 and flag_odd == 1:
		print(1)
	else:
		print(2)


n = int(input())
for i in range(n):
	d = []
	m = int(input())
	b = input()
	o = 0
	e = 0
	for i in range(m):
		if b[i] == '1':
			if i % 2 == 0:
				e = e + 1
			else:
				o = o + 1
	if e > 0 and o > 0:
		print(1)
	else:
		print(2)


test = int(input())
for i in range(0, test):
	n = int(input())
	st = input()
	(ev, od) = (0, 0)
	for i in range(0, n):
		if st[i] == '1':
			if i % 2 == 0:
				ev = ev + 1
			else:
				od = od + 1
	if od > 0 and ev > 0:
		print(1)
	else:
		print(2)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	s = input()
	v1 = None
	for i in range(n):
		if s[i] == '1':
			if v1 != None and v1 != i % 2:
				print(1)
				return
			v1 = i % 2
	print(2)
for t in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	odd = 0
	even = 0
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if even > 0 and odd > 0:
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	o = False
	p = s.index('1')
	for i in range(p + 1, n):
		if s[i] == '1':
			x = i - p
			if x % 2 != 0:
				o = True
				break
			p = i
	if o == True:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = False
	b = False
	for i in range(n):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
	if a > 0 and b > 0:
		print(1)
	else:
		print(2)


T = int(input())
while T:
	T -= 1
	n = int(input())
	s = input()
	if '11' in s:
		print(1)
	elif n == 3:
		print(2)
	else:
		a = 0
		b = 0
		c = []
		for i in range(n):
			if int(s[i]):
				if c:
					if (-c[-1] + i) % 2:
						print(1)
						break
					else:
						c.append(i)
				else:
					c.append(i)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	fin0 = False
	y = True
	cnt0 = 1
	z = False
	for i in range(n - 1):
		if s[i] == s[i + 1] == '1':
			print('1')
			y = False
			break
		if s[i] == '1':
			z = True
		if s[i] == s[i + 1] == '0':
			cnt0 += 1
		elif s[i] != s[i + 1]:
			if cnt0 % 2 == 0 and z:
				fin0 = True
			cnt0 = 1
	if y:
		if fin0:
			print('1')
		else:
			print('2')


for _ in range(int(input())):
	n = int(input())
	s = input()
	v = []
	odd = 0
	for i in range(n):
		if s[i] == '1':
			v.append(i)
	for j in range(len(v) - 1):
		if abs(v[j] - v[j + 1]) % 2 != 0:
			odd += 1
			break
	if odd == 0:
		print(2)
	else:
		print(1)


f = int(input())
for _ in range(f):
	n = int(input())
	h = input()
	a = b = False
	for i in range(n):
		if h[i] == '1':
			if i % 2:
				a = True
			else:
				b = True
	print(1 if a & b else 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if '11' in s:
		print(1)
	elif n <= 3:
		if '101' in s:
			print(2)
	else:
		arr = []
		for i in range(n):
			if s[i] == '1':
				arr += [i]
		flag = 1
		for i in range(len(arr) - 1):
			if (arr[i + 1] - arr[i]) % 2 == 1:
				print(1)
				flag = 0
				break
		if flag:
			print(2)


for i in range(int(input())):
	N = int(input())
	s = input()
	e = 0
	o = 0
	for j in range(N):
		if s[j] == '1':
			if j % 2 == 0:
				e = e + 1
			else:
				o = o + 1
	if e > 0 and o > 0:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	l2 = []
	for i in range(n):
		if l[i] == '1':
			l2.append(i + 1)
	n2 = len(l2)
	c = 0
	for i in range(n2 - 1):
		if l2[i + 1] - l2[i] == 1:
			c = 1
			break
		elif (l2[i + 1] - l2[i]) % 2 == 0:
			c = 2
		elif (l2[i + 1] - l2[i]) % 3 == 0:
			c = 1
			break
		elif (l2[i + 1] - l2[i]) % 2 == 1 and (l2[i + 1] - l2[i]) % 3 != 0:
			c = 1
			break
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = b = False
	for i in range(n):
		if s[i] == '1':
			if i % 2:
				a = True
			else:
				b = True
	print(1 if a & b else 2)


for _ in range(int(input())):
	n = int(input())
	x = input()
	y = []
	for i in range(len(x)):
		if x[i] == '1':
			y.append(i)
	k = []
	k1 = []
	c = 0
	d = 0
	for j in range(len(y) - 1):
		if (y[j + 1] - y[j]) % 2 == 0:
			c = 1
		else:
			d = 1
		if c == 1 and d == 1:
			break
	if d == 1:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	q = [0, 0]
	for i in range(n):
		if s[i] == '1':
			q[i % 2] += 1
	if q[0] > 0 and q[1] > 0:
		print(1)
	else:
		print(2)


import re
T = int(input())
for i in range(T):
	N = int(input())
	B = input()
	if re.match('^.*1([0][0])*1.*$', B):
		print('1')
	else:
		print('2')


def findmin(N, strd):
	pass
	list1 = []
	for i in range(len(strd)):
		if strd[i] == '1':
			list1.append(i)
	min = len(strd)
	for i in range(len(list1) - 1):
		diff = list1[i + 1] - list1[i]
		if diff % 2 == 1:
			return 1
		if min >= diff:
			min = diff
	return 2
A = input()
for i in range(int(A)):
	nd = int(input())
	strd = input()
	outd = findmin(nd, strd)
	print(outd)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	(count, one, flag) = (0, 0, 0)
	for i in range(n):
		if s[i] == '1':
			one = i
			break
	for i in range(one + 1, n):
		if s[i] == '0':
			count += 1
		elif count % 2 == 0:
			flag = 1
			break
		else:
			count = 0
	if flag == 1:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	n = int(input())
	a = str(input())
	(got_even_pos_1, got_odd_pos_1) = (False, False)
	for i in range(n):
		if a[i] == '1':
			if (i + 1) % 2 == 0:
				got_even_pos_1 = True
			else:
				got_odd_pos_1 = True
	print(1 if got_even_pos_1 and got_odd_pos_1 else 2)


n = int(input())
for i in range(n):
	n1 = int(input())
	l = input()
	prev = -1
	ans = 2
	for i in range(n1):
		if l[i] == '1':
			if prev == -1:
				prev = i
			elif (i - prev) % 2:
				ans = 1
				break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [i for i in s]
	Lst = []
	for i in range(0, len(l)):
		if l[i] == '1':
			Lst.append(i)
	diff_list = []
	for i in range(1, len(Lst)):
		diff_list.append(Lst[i] - Lst[i - 1])
	count = 0
	for i in diff_list:
		if i % 2 == 1:
			count += i
	if count >= 1:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	l = int(input())
	s = input()
	even = 0
	odd = 0
	for x in range(l):
		if s[x] == '1':
			if x % 2 == 0:
				even = 1
			else:
				odd = 1
	print(1 if odd > 0 and even > 0 else 2)


for _ in range(int(input())):
	N = int(input())
	S = list(map(int, list(input())))
	tx1 = 0
	tx2 = 0
	tx3 = 0
	for x in range(0, N, 2):
		if S[x]:
			tx1 = 1
			break
	for x in range(1, N, 2):
		if S[x]:
			tx2 = 1
			break
	for x in range(2, N, 2):
		if S[x]:
			tx3 = 1
			break
	if tx1 and tx2 or (tx2 and tx3):
		print(1)
	else:
		print(2)


n = int(input())
out = []
for i in range(n):
	x = int(input())
	s = input()
	mindistance = x
	for j in range(x):
		if s[j] == '1':
			for k in range(j + 1, x):
				if s[k] == '1':
					distance = k - j
					break
			if distance > 2:
				if distance % 2 == 0:
					distance = 2
				else:
					distance = 1
			if distance < mindistance:
				mindistance = distance
	out += [int(mindistance)]
for i in out:
	print(i)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	odd = 0
	evn = 0
	for i in range(len(s)):
		if s[i] == '1':
			if i % 2 == 0:
				evn += 1
			else:
				odd += 1
	if odd > 0 and evn > 0:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	a = int(input())
	x = str(input())
	m = a
	n = x.index('1')
	for i in range(a):
		if x[i] == '1':
			if n < i:
				k = i - n
				while k >= 3:
					k -= 2
				if m > k:
					m = k
				n = i
	print(m)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	even = 0
	odd = 0
	for i in range(n):
		if data[i] == '1':
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if even > 0 and odd > 0:
		print(1)
	else:
		print(2)


testCase = int(input())
for i in range(0, testCase):
	Size = int(input())
	S = input()
	min_length = Size
	even = 0
	odd = 0
	for j in range(0, Size):
		if S[j] == '1':
			if j % 2 == 0:
				even = even + 1
			else:
				odd = odd + 1
	if even > 0 and odd > 0:
		print(1)
	else:
		print(2)


tc_no = int(input())
for tcs in range(tc_no):
	m = int(input())
	p = input()
	odd = 0
	even = 0
	for i in range(m):
		if p[i] == '1':
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if even > 0 and odd > 0:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = []
	if n < 3:
		if s[0] == s[1]:
			print(1)
		else:
			print(2)
	elif n == 3:
		if s[0] == s[-1]:
			print(2)
		else:
			print(1)
	else:
		for i in range(n):
			if s[i] == '1':
				l.append(i % 2)
		if 0 in l and 1 in l:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	while i < n:
		if s[i] == '1':
			p = s.find('1', i + 1)
			if p == -1:
				print('2')
				break
			elif (p - i) % 2:
				print('1')
				break
			else:
				i = p
				continue
		i += 1


T = int(input())
for i in range(T):
	N = int(input())
	A = list(input().strip(' '))
	B = []
	T = []
	i = 0
	for x in A:
		if x == '1':
			B.append(i)
		i += 1
	for j in range(len(B) - 1):
		if (B[j + 1] - B[j]) % 2 == 1:
			print(1)
			break
		elif j == len(B) - 2:
			print(2)


for k in range(int(input())):
	n = int(input())
	b = input()
	ty = []
	for i in range(n):
		if b[i] == '1':
			ty.append(i)
	for i in range(1, len(ty)):
		if (ty[i] - ty[i - 1]) % 2 != 0:
			print(1)
			break
	else:
		print(2)