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 maximize the value of X after performing the operation. Help Chef in determining the value of Y which will maximize 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 containing the length of binary string S.
- The second line of input contains the binary string S.

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

For each test case, output on a new line, the value of Y which will maximize 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 ------ 
1
2
1
2

----- explanation 1 ------ 
Test case $1$: Since $S = 10$ is the binary representation of $2$, the current value of $X = 2$. On choosing $Y = 1$, $X$ becomes $2 \oplus \lfloor \frac{2}{2^{1}} \rfloor = 3$. We can show that this is the maximum 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 = 2$, $X$ becomes $3 \oplus \lfloor \frac{3}{2^{2}} \rfloor = 3$. We can show that this is the maximum 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 = 1$, $X$ becomes $5 \oplus \lfloor \frac{5}{2^{1}} \rfloor = 7$. We can show that this is the maximum 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 = 2$, $X$ becomes $6 \oplus \lfloor \frac{6}{2^{2}} \rfloor = 7$. We can show that this is the maximum value of $X$ we can achieve after one operation.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

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


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


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n):
		if s[i] != '1':
			print(i)
			break
	else:
		print(n)


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


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


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in s:
		if i == '1':
			count += 1
		else:
			break
	print(count)


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


t = int(input())
for x in range(t):
	n = int(input())
	a = input()
	i = 1
	while i < n and a[i] == '1':
		i += 1
	print(i)


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(input())
	c = 0
	while c < n and l[c] == '1':
		c += 1
	print(c)


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


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


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	S = s.split()
	L = len(S)

	def a1():
		pass
	c = 1
	for i in range(1, l):
		if s[i] == '1':
			c = c + 1
		else:
			break
	print(c)


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


T = int(input())
x = 0
for i in range(T):
	N = int(input())
	S = input()
	for j in range(N):
		if S[j] == '1':
			x += 1
		else:
			break
	print(x)
	x = 0


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


for t in range(int(input())):
	length = int(input())
	binary_s = input()
	print(binary_s.split('0')[0].count('1'))


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = int(s, 2)
	maxN = float(0)
	y = 0
	for i in range(1, n + 1):
		xor = x ^ x >> i
		if xor > maxN:
			y = i
			maxN = xor
	print(y)


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


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


for tc in range(int(input())):
	n = int(input())
	s = input()
	ze = n
	for i in range(n):
		if s[i] == '0':
			ze = i
			break
	print(ze)


for i in range(int(input())):
	x = int(input())
	a = input()
	if a.count('1') == x:
		print(x)
	else:
		print(a.index('0'))


num_cases = int(input())
for i in range(num_cases):
	n = int(input())
	s = input().strip()
	zero_index = s.find('0')
	print(zero_index if zero_index != -1 else n)


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


for i in range(int(input())):
	l = int(input())
	s = str(input())
	j = 1
	while j < l and s[j] == '1':
		j += 1
	print(j)


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


import math

def checking(n, s):
	li = list(s)
	c = 0
	if '0' in li:
		for i in li:
			if i == '1':
				c += 1
			if i == '0':
				return c
	return n
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(checking(n, s))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	for (i, j) in enumerate(s):
		if j == '0':
			print(i)
			break
	else:
		print(n)


def main():
	T = int(input())
	while T:
		n = int(input())
		s = input()[:n]
		cnt = 0
		for i in s:
			if i == '0':
				break
			else:
				cnt += 1
		print(cnt)
		T -= 1
main()


for j in range(int(input())):
	x = int(input())
	y = input()
	i = 1
	while i < x and y[i] == '1':
		i += 1
	print(i)


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


import math as m
for i in range(int(input())):
	a = int(input())
	x = input()
	i = 1
	while i < a and x[i] == '1':
		i += 1
	print(i)


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


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


def single_op(n, s):
	for op in range(n):
		if s[op] == '0':
			return op
	return n
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(single_op(n, s))


def single_op(n, s, op=1):
	while op < n and s[op] == '1':
		op += 1
	return op
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(single_op(n, s))


g = int(input())
while g != 0:
	n = int(input())
	s = input()
	c = 0
	for i in s:
		if i == '1':
			c += 1
		else:
			break
	print(c)
	g -= 1