Chef has the binary representation S of a number X with him. He can modify the number by applying the following operation exactly once:
Make X := X \oplus \lfloor \frac{X}{2^{Y}} \rfloor, where (1 ≤ Y ≤ |S|) and \oplus denotes the [bitwise XOR operation].

Chef wants to minimize the value of X after performing the operation. Help Chef in determining the value of Y which will minimize the value of X after the operation.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of inputs:
- The first line contains the length of the binary string S.
- The second line contains the binary string S.

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

For each test case, output on a new line, the value of Y which will minimize the value of X after the operation.

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

$1 ≤ T ≤ 5 \cdot 10^{4}$
$1 ≤ |S| ≤ 10^{5}$
- The sum of $|S|$ over all test cases won't exceed $5 \cdot 10^{5}$.
$S$ contains the characters $0$ and $1$ only.

----- Sample Input 1 ------ 
4
2
10
2
11
3
101
3
110

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

----- explanation 1 ------ 
Test case $1$: Since $S = 10$ is the binary representation of $2$, the current value of $X = 2$. On choosing $Y = 2$, $X$ becomes $2 \oplus \lfloor \frac{2}{2^{2}} \rfloor = 2$. We can show that this is the minimum value of $X$ we can achieve after one operation.

Test case $2$: Since $S = 11$ is the binary representation of $3$, the current value of $X = 3$. On choosing $Y = 1$, $X$ becomes $3 \oplus \lfloor \frac{3}{2^{1}} \rfloor = 2$. We can show that this is the minimum value of $X$ we can achieve after one operation.

Test case $3$: Since $S = 101$ is the binary representation of $5$, the current value of $X = 5$. On choosing $Y = 2$, $X$ becomes $5 \oplus \lfloor \frac{5}{2^{2}} \rfloor = 4$. We can show that this is the minimum value of $X$ we can achieve after one operation.

Test case $4$: Since $S = 110$ is the binary representation of $6$, the current value of $X = 6$. On choosing $Y = 1$, $X$ becomes $6 \oplus \lfloor \frac{6}{2^{1}} \rfloor = 5$. We can show that this is the minimum value of $X$ we can achieve after one operation.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	i = 1
	while i < n and s[i] == '0':
		i += 1
	print(i)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	j = 1
	while j < n and s[j] == '0':
		j += 1
	print(j)


for i in range(int(input())):
	ka = int(input())
	vy = input()
	flag = True
	for i in range(1, ka):
		if vy[i] == '1':
			print(i)
			flag = False
			break
	if flag:
		print(ka)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 1
	i = 1
	while i < len(s):
		if s[i] == '0':
			count += 1
			i += 1
		else:
			break
	print(count)


t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	count = 1
	for j in range(1, len(s)):
		if s[j] == '0':
			count += 1
			continue
		else:
			break
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	s = input().strip()
	c = 1
	for j in range(1, N):
		if s[j] == '1':
			break
		c += 1
	print(c)


import math
t = int(input())
while t:
	n = int(input())
	s = input()
	q = 1
	while q < n and s[q] == '0':
		q += 1
	print(q)
	t -= 1


t = int(input())
for i in range(t):
	l = int(input())
	binary = input()
	ans = 1
	f = 0
	for i in binary:
		if i == '1':
			f += 1
		if f == 1 and i == '0':
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	ans = 1
	for j in range(0, l - 1):
		if s[j + 1] == '0':
			ans += 1
		else:
			break
	print(ans)


for tc in range(int(input())):
	n = int(input())
	s = input()
	ans = n
	for i in range(1, n):
		if s[i] == '1':
			ans = i
			break
	print(ans)


for t in range(int(input())):
	l = int(input())
	s = input()
	c = 1
	while c < l and s[c] == '0':
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = False
	for i in range(1, n):
		if s[i] == '1':
			print(i)
			flag = True
			break
	if flag == False:
		print(n)


msd = int(input())
for aj in range(msd):
	n = int(input())
	S = str(input())
	y = n
	for i in range(1, n):
		if S[i] == '1':
			y = i
			break
	print(y)


for _ in range(int(input())):
	a = int(input())
	n = input()
	c = int(n, 2)
	e = {}
	for i in range(1, a + 1):
		d = c ^ c >> i
		e[i] = d
	print(min(e, key=e.get))


for t in range(int(input())):
	l = int(input())
	s = input()
	for i in range(1, l):
		if s[i] == '1':
			print(i)
			break
	else:
		print(l)


def main():
	hem = int(input())
	while hem > 0:
		ant = int(input())
		kum = input()
		har = 1
		for i in range(1, ant):
			if kum[i] == '1':
				break
			else:
				har += 1
		print(har)
		hem -= 1
main()


T = int(input())
for tc in range(T):
	slen = int(input())
	s = input()
	min = 1
	while min < slen and s[min] == '0':
		min += 1
	print(min)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	first = S.index('1')
	if '1' not in S[first + 1:]:
		print(N - first)
	else:
		second = S[first + 1:].index('1')
		print(second + first + 1)


from math import inf
for _ in range(int(input())):
	n = int(input())
	s1 = int(input(), 2)
	s2 = s1
	s2 >>= 1
	count = 1
	res = 0
	minn = inf
	while s2 >= 0:
		if s1 ^ s2 < minn:
			minn = s1 ^ s2
			res = count
		count += 1
		if s2 == 0:
			break
		s2 >>= 1
	print(res)


for k in range(int(input())):
	n1 = int(input())
	n2 = input()
	n2 = format(int(n2, 2), 'b')
	f = 1
	d = 0
	s = 1
	if n1 > 0:
		for i in range(1, n1):
			if n2[i] == '1':
				break
			f += 1
		if d == 0 and s == 1:
			print(f)
		else:
			print(0)


n = int(input())
for q in range(n):
	l = int(input())
	s = input()
	c = 1
	while c < l and s[c] == '0':
		c += 1
	print(c)


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	s = s[1:]
	s = s + '1'
	if s.count('0') == 0:
		print(1)
	else:
		for val in s:
			if val == '1':
				print(s.index(val) + 1)
				break


for _ in range(int(input())):
	x = int(input())
	s = input()
	y = 1
	for i in range(x - 1):
		if s[i + 1] == '1':
			break
		else:
			y += 1
	print(y)


import math

def solve(n, s):
	x = int(s, 2)
	if x == 0:
		return 1
	i = s.find('1', 1)
	if i == -1:
		return n
	return i
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


n = int(input())
for i in range(n):
	len_num = int(input())
	num = input()
	y = len_num
	for j in range(1, len_num):
		if num[j] == '1':
			y = j
			break
	print(y)


T = int(input())
for _ in range(0, T):
	l = int(input())
	s = input()
	y = 1
	for i in range(0, l - 1):
		if s[i + 1] == '1':
			break
		else:
			y += 1
	print(y)


n = int(input())
for _ in range(0, n):
	a = int(input())
	b = input()
	x = 1
	for i in range(0, a - 1):
		if b[i + 1] == '1':
			break
		else:
			x += 1
	print(x)


n = int(input())
for i in range(0, n):
	a = int(input())
	b = input()
	c = 1
	for i in range(0, a - 1):
		if b[i + 1] == '1':
			break
		else:
			c += 1
	print(c)


for i in range(int(input())):
	a = int(input())
	b = input()
	s = 2
	inde = 0
	for j in range(len(b)):
		if b[j] == '1':
			s -= 1
			inde = j
		if s == 0:
			break
	if s == 0:
		print(inde)
	else:
		print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = n
	for i in range(1, len(s)):
		if s[i] == '1':
			a = i
			break
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = 1
	for i in range(1, len(s)):
		if s[i] == '1':
			break
		res += 1
	print(res)


t = int(input())
for i in range(t):
	lens = int(input())
	s = input()
	for i in range(lens - 1):
		if s[i + 1] == '1':
			lens = i + 1
			break
	print(lens)


for i in range(int(input())):
	n = int(input())
	c = input()
	l = []
	l[:] = c
	p = l[1:]
	if '1' in p:
		print(p.index('1') + 1)
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = n
	for i in range(1, n):
		if s[i] == '1':
			m = i
			break
	print(m)


def main():
	abc = int(input())
	while abc > 0:
		nmb = int(input())
		sda = input()
		cvx = 1
		for i in range(1, nmb):
			if sda[i] == '1':
				break
			else:
				cvx += 1
		print(cvx)
		abc -= 1
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = int(s, 2)
	m = n
	for i in range(1, n):
		if s[i] == '1':
			m = i
			break
	print(m)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = n
	for i in range(1, n):
		if s[i] == '1':
			m = i
			break
	print(m)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = n
	for i in range(1, n):
		if s[i] == '1':
			a = i
			break
	print(a)


x = int(input())
for i in range(x):
	n = int(input())
	s = input()
	flag = int(0)
	for j in range(1, n):
		if s[j] == '1':
			print(j)
			flag = 1
			break
	if flag == 0:
		print(n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		if s[i] == '0' or (s[i] == '1' and i == 0):
			c += 1
		else:
			break
	print(c)


for tc in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for x in range(len(s)):
		if s[x] == '0' or (s[x] == '1' and x == 0):
			c += 1
		else:
			break
	print(c)


test = int(input())
for i in range(test):
	n = int(input())
	string = input()
	cnt = 0
	string += '1'
	flag = True
	for i in string:
		if i == '1' and (not flag):
			break
		cnt += 1
		if i == '1':
			flag = False
	print(cnt)


n = int(input())
for i in range(n):
	t = int(input())
	s = input()
	l = 0
	for x in range(len(s)):
		if s[x] == '1' and x == 0 or s[x] == '0':
			l += 1
		else:
			break
	print(l)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(1, n):
		if s[i] == '1':
			ans = i
			break
	if ans == 0:
		print(n)
	else:
		print(ans)


vishnesh = int(input())
for vish in range(vishnesh):
	n = int(input())
	s = input()
	a1 = n
	if '1' in s:
		a1 = s.index('1')
	a1 = a1 + 1
	s2 = s[1:]
	a2 = n - 1
	if '1' in s2:
		a2 = s2.index('1')
	print(a1 + a2)


for _ in range(int(input())):
	x = int(input())
	s = input()
	val = 1
	for i in range(1, x):
		val += 1
		if s[i] == '1':
			val = i
			break
	print(val)


z = int(input())
while z:
	x = int(input())
	y = input()
	for i in range(1, x):
		if y[i] == '1':
			x = i
			break
	print(x)
	z -= 1


for _ in range(int(input())):
	num = int(input())
	arr = input()
	val = 1
	for i in range(1, num):
		val += 1
		if arr[i] == '1':
			val = i
			break
	print(val)


import math
try:
	t = int(input())
	for i in range(t):
		n = int(input())
		m = input()
		m = list(m)
		m.append(' ')
		result = 0
		for j in range(0, n):
			result += 1
			if m[j + 1] == '1':
				break
		print(result, end='\n')
except:
	pass


test_case = int(input())
for i in range(test_case):
	X = int(input())
	Y = input()
	Y += '1'
	result = 1
	for i in range(1, len(Y)):
		if Y[i] == '1':
			print(result)
			break
		result += 1


t = int(input())
while t != 0:
	n = int(input())
	k = input()
	c = n
	for i in range(1, n):
		if k[i] == '1':
			c = i
			break
	print(c)
	t -= 1