Chef has a binary string S of length N.

Chef can perform the following operation on the string:
Choose any substring of S;
Remove the chosen substring from S;
Concatenate the remaining parts of the string S, obtained after removing the substring.

Find the length of the longest prefix having all 1s you can achieve, by performing the above operation at most once.

Note: A prefix of a string is obtained by deleting some (possibly zero) characters from the end of string S.

------ 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 a single integer N, the length of the binary string.
- The next line contains the binary string S.

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

For each test case, print in a new line, the length of the longest prefix having all 1s you can achieve, by performing the operation at most once.

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

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

----- Sample Input 1 ------ 
3
4
1010
6
011011
11
01011011101

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

----- explanation 1 ------ 
Test case $1$: Chef can choose the substring $S[2, 2] = 0$. On removal of the substring, the remaining parts are $1$ and $10$. On concatenating these parts, the final string obtained is $110$.  
The longest prefix in the final string having all $1$s is $11$, having a length $2$.

It can be proven that we cannot obtain a prefix of length greater than $2$ having all $1$s using at most one operation.

Test case $2$: Chef can choose the substring $S[1, 4] = 0110$. On removal of the substring, the remaining part is $11$.  
The longest prefix in the final string having all $1$s is $11$, having a length $2$.

It can be proven that we cannot obtain a prefix of length greater than $2$ having all $1$s using at most one operation.

Test case $3$: Chef can choose the substring $S[1, 6] = 010110$. On removal of the substring, the remaining part is $11101$.  
The longest prefix in the final string having all $1$s is $111$, having a length $3$.

It can be proven that we cannot obtain a prefix of length greater than $3$ having all $1$s using at most one operation.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	p = input()
	s = 0
	l = []
	for i in range(n):
		if p[i] == '0':
			if s > 0:
				l.append(s)
			s = 0
		else:
			s += 1
	if s > 0:
		l.append(s)
	if l == []:
		print(0)
	elif len(l) == 1:
		print(l[0])
	elif p[0] == '0':
		print(max(l))
	else:
		print(l[0] + max(l[1:]))


for tc in range(int(input())):
	n = input()
	s = input()
	i = s.find('0')
	if i == -1:
		print(len(s))
		continue
	t = s[i:]
	print(max((len(u) for u in t.split('0'))) + i)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if '0' not in s:
		print(n)
	elif s[0] == '1':
		i = 0
		while s[i] == '1':
			i = i + 1
		l = []
		c = 0
		s = s + '0'
		for j in range(i, len(s)):
			if s[j] == '1':
				c = c + 1
			else:
				l.append(c)
				c = 0
		print(i + max(l))
	else:
		l = []
		c = 0
		s = s + '0'
		for j in range(0, len(s)):
			if s[j] == '1':
				c = c + 1
			else:
				l.append(c)
				c = 0
		print(max(l))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	cnt = 0
	one = []
	for i in s:
		if i == '1':
			cnt += 1
		elif i == '0':
			if cnt != 0:
				one.append(cnt)
			cnt = 0
	if cnt != 0:
		one.append(cnt)
	if len(one) == 0:
		print(0)
	elif s[0] == '0':
		print(max(one))
	else:
		print(one[0] + max(one[1:]) if len(one) != 1 else one[0])


for _ in range(int(input())):
	n = int(input())
	arr = input()
	fi = 0
	i = 0
	while i < n and arr[i] == '1':
		fi += 1
		i += 1
	if fi == n:
		print(fi)
	else:
		cnt = 0
		s = 0
		for k in range(i, n):
			if arr[k] == '1':
				s += 1
				if s > cnt:
					cnt = s
			else:
				s = 0
		cnt += fi
		print(cnt)


T = input()
for i in range(int(T)):
	N = int(input())
	a = input()
	list0 = [i for i in a.split('0')]
	list1 = list0[1:]
	list1.sort()
	if len(list0) == 1:
		largest = len(list0[0])
	else:
		largest = len(list1[-1]) + len(list0[0])
	print(largest)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def ans():
	pora = int(input())
	string = input()
	lavadaval = 0
	supermova = 0
	if string == '1' * pora:
		print(pora)
		return
	elif string[0] == '0':
		for i in range(pora):
			if string[i] == '0':
				lavadaval = max(lavadaval, supermova)
				supermova = 0
			else:
				supermova += 1
		lavadaval = max(lavadaval, supermova)
		print(lavadaval)
		return
	else:
		puku = 0
		jai = 0
		for i in range(pora):
			if string[i] == '1':
				puku += 1
			else:
				jai = i
				break
		for i in range(jai, pora):
			if string[i] == '0':
				lavadaval = max(lavadaval, supermova)
				supermova = 0
			else:
				supermova += 1
		lavadaval = max(lavadaval, supermova)
		lavadaval += puku
		print(lavadaval)
		return
for _ in range(int(input())):
	ans()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	idx = 0
	while idx < n and s[idx] == '1':
		idx += 1
	if idx == n:
		print(n)
	elif idx == 0:
		ans = 0
		curr = 0
		for i in range(len(s)):
			if s[i] == '1':
				curr += 1
			else:
				ans = max(ans, curr)
				curr = 0
		ans = max(ans, curr)
		print(ans)
	else:
		ans = 0
		curr = 0
		for i in range(idx, len(s)):
			if s[i] == '1':
				curr += 1
			else:
				ans = max(ans, curr)
				curr = 0
		ans = max(ans, curr)
		print(ans + idx)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	s2 = 0
	s1 = 0
	f = 0
	for i in s:
		if i == '1':
			c += 1
		else:
			if f == 0:
				f = 1
				s1 = c
			else:
				s2 = max(c, s2)
			c = 0
	s2 = max(c, s2)
	if s[0] == '0':
		print(max(s1, s2))
	else:
		print(s1 + s2)


for _ in range(int(input())):
	n = input()
	s = input()
	try:
		index = s.index('0')
		s = s[index:]
		print(max((len(i) for i in s.split('0'))) + index)
	except:
		print(n)


for _ in range(int(input())):
	t = int(input())
	str1 = input()
	if str1.count('1') == 0:
		print(0)
	else:
		str1 = str1.split('0')
		if len(str1) == 1:
			print(len(str1[0]))
		elif str1[0] == '0':
			print(max([len(x) for x in str1]))
		else:
			print(max([len(str1[0]) + max([len(x) for x in str1[1:]]), max([len(x) for x in str1])]))


for _ in range(int(input())):
	n = int(input())
	s = str(input()).strip()
	s = s.lstrip('1')
	print(n - len(s) + max((len(sp) for sp in s.split('0'))))


for _ in range(int(input())):
	_ = input()
	s = input() + '0'
	n = len(s)
	cnts = []
	(cnt, max_cnt) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			cnt += 1
		elif cnt > 0:
			cnts.append(cnt)
			max_cnt = max(cnt, max_cnt)
			cnt = 0
	if s[0] == '0' or len(cnts) == 1:
		print(max_cnt)
	else:
		print(cnts[0] + max(cnts[1:]))


def largest_sub(s):
	maxi = 0
	count = 0
	for i in s:
		if i == '0':
			count = 0
			continue
		count += 1
		if count > maxi:
			maxi = count
	return maxi
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s[0] == '0':
		print(largest_sub(s))
	elif s.count('0') == 0:
		print(n)
	else:
		t = 0
		for i in s:
			if i == '0':
				break
			t += 1
		x = s.lstrip('1')
		print(largest_sub(x) + t)


def solve():
	n = int(input())
	s = input()
	one = 0
	pre = 0
	mx = 0
	j = 0
	while j < n and s[j] == '1':
		j += 1
		pre += 1
	for i in range(j, n):
		if s[i] == '1':
			one += 1
		else:
			mx = max(mx, one)
			one = 0
	mx = max(mx, one)
	print(mx + pre)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = input()
	s = a.split('0')
	f = []
	ma = 0
	for i in s:
		if i == '':
			continue
		else:
			f.append(len(i))
			ma = max(ma, len(i))
	if a[0] == '0':
		print(ma)
	elif len(f) > 1:
		print(max(ma, f[0] + max(f[1:])))
	else:
		print(ma)


from functools import reduce
import math

def vout(v):
	return ' '.join(map(str, v))

def main(is_testCases=True):
	testCases = 1
	if is_testCases:
		testCases = int(input())
	for _ in range(testCases):
		n = int(input())
		s = input()
		index = s.find('0')
		if index == -1:
			print(n)
		else:
			answer = 0
			current = 0
			for i in range(index + 1, len(s)):
				if s[i] == '1':
					current += 1
					answer = max(answer, current)
				else:
					current = 0
			print(answer + index)
main()


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	l = s.split('0')
	if int(s) == 0:
		print(0)
	elif l[0] == '':
		print(len(max(l)))
	elif len(l) == 1:
		print(len(l[0]))
	elif len(l[0]) != len(max(l)):
		print(len(l[0]) + len(max(l)))
	elif len(max(l)) == len(l[0]):
		x = len(l[0])
		l.remove(l[0])
		print(x + len(max(l)))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	series = 0
	if s[0] == '1':
		k = 0
		while k < n and s[k] == '1':
			ans = ans + 1
			k = k + 1
		ts = 0
		for i in range(k, n):
			if s[i] == '0':
				if ts > series:
					series = ts
				ts = 0
			else:
				ts = ts + 1
		if ts > series:
			series = ts
	else:
		ts = 0
		for j in s:
			if j == '0':
				if ts > series:
					series = ts
				ts = 0
			else:
				ts = ts + 1
			if ts > series:
				series = ts
	ans = ans + series
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	maxi = 0
	first = 0
	if s[0] == '0':
		i = 1
		c = 0
		while i < n:
			if s[i] == '1':
				c += 1
			else:
				maxi = max(maxi, c)
				c = 0
			i += 1
		maxi = max(maxi, c)
	else:
		i = 0
		while i < n and s[i] == '1':
			first += 1
			i += 1
		c = 0
		maxi = 0
		while i < n:
			if s[i] == '1':
				c += 1
			else:
				maxi = max(maxi, c)
				c = 0
			i += 1
		maxi = max(maxi, c)
	print(first + maxi)


for _ in range(int(input())):
	input()
	s = input()
	i = s.find('0')
	if i == -1:
		print(len(s))
	else:
		print(max((len(u) for u in s[i:].split('0'))) + i)


for _ in range(int(input())):
	n = int(input())
	s = input()
	zero = s.find('0')
	if zero == -1:
		print(len(s))
		continue
	t = s[zero:]
	print(max((len(u) for u in t.split('0'))) + zero)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	c = 0
	for i in range(n):
		if s[i] == '1':
			c += 1
		else:
			l.append(c)
			c = 0
	l.append(c)
	maxPrefix = l[0]
	m = 0
	for i in range(1, len(l)):
		if l[i] > m:
			m = l[i]
	print(maxPrefix + m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(str, input().split('0')))
	m = 0
	ex = 0
	if len(a[0]) > 0:
		ex = len(a[0])
		a.remove(a[0])
	for i in range(len(a)):
		if len(a[i]) > m:
			m = len(a[i])
	print(m + ex)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	if s[0] == '0':
		end = 1
		while end < n:
			counter = 0
			if s[end] == '1':
				while end < n and s[end] == '1':
					counter += 1
					end += 1
			ans = max(ans, counter)
			end += 1
		print(ans)
	elif s[0] == '1':
		pre = 0
		end = 0
		while end < n and s[end] == '1':
			pre += 1
			end += 1
		while end < n:
			counter = 0
			if s[end] == '1':
				while end < n and s[end] == '1':
					counter += 1
					end += 1
			ans = max(ans, counter)
			end += 1
		print(ans + pre)


t = int(input())
while t > 0:
	t -= 1
	l = int(input())
	s = input()
	m1 = 0
	f = 0
	i = 0
	m3 = 0
	while i < l:
		f = 0
		c = 0
		while i < l and s[i] != '0':
			if i == 0:
				f = 1
			c += 1
			i += 1
		if f == 1:
			m3 = c
		elif c > m1:
			m1 = c
		i += 1
	if m3 > 0:
		print(m3 + m1)
	else:
		print(m1)


def helper(arr):
	k = 1
	ans = 0
	left = -1
	h = []
	arr = str(arr)
	lst = [0 for i in range(len(arr))]
	big = float('-inf')
	if '0' not in arr:
		return len(arr)
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == '1' and (i + 1 >= len(arr) or arr[i + 1] == '0'):
			lst[i] = 1
		elif arr[i] == '1' and (i + 1 < len(arr) and arr[i + 1] == '1'):
			lst[i] = lst[i + 1] + 1
		big = max(big, lst[i])
	if arr[0] == '0':
		return big
	else:
		for i in range(len(arr)):
			if arr[i] == '0':
				return lst[0] + max(lst[i:])
for i in range(int(input())):
	n = int(input())
	print(helper(str(input())))


AmXz = 0
for loop in range(int(input())):
	PnNp = int(input())
	l = list(input())
	DeL = 0
	cnt = 0
	DelloiTTe = 0
	for i in range(PnNp):
		if l[i] == '1':
			DelloiTTe += 1
		else:
			break
	for i in range(DelloiTTe, PnNp):
		if l[i] == '1':
			cnt += 1
		else:
			cnt = 0
		DeL = max(cnt, DeL)
	print(DeL + DelloiTTe)


for loop in range(int(input())):
	n = int(input())
	l = list(input())
	ans = 0
	cnt = 0
	preOnes = 0
	for i in range(n):
		if l[i] == '1':
			preOnes += 1
		else:
			break
	for i in range(preOnes, n):
		if l[i] == '1':
			cnt += 1
		else:
			cnt = 0
		ans = max(cnt, ans)
	print(ans + preOnes)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	best = 0
	for (key, val) in groupby(s):
		l = len(list(val))
		if key == '1':
			best = max(best, l)
	if s[0] == '0':
		print(best)
	else:
		first = 0
		cnt = 0
		for i in range(n):
			if s[i] == '1':
				cnt += 1
			elif first == 0:
				first = cnt
				cnt = 0
			elif cnt != 0:
				best = max(best, first + cnt)
				cnt = 0
		if cnt != 0:
			best = max(best, first + cnt)
		print(best)


for testcase in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	pre = 0
	z = 0
	for i in range(n):
		if s[i] == '1':
			pre += 1
		else:
			z = i
			break
	t = 0
	for i in range(i + 1, n):
		if s[i] == '1':
			count += 1
		else:
			t = max(count, t)
			count = 0
	t = max(t, count)
	print(t + pre)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())

def f():
	(n, s) = (IN(), IS())
	i = 0
	while i < n and s[i] != '0':
		i += 1
	(r, c) = (0, 0)
	for x in range(i + 1, n):
		if s[x] == '1':
			c += 1
		else:
			r = max(r, c)
			c = 0
	r = max(r, c)
	return i + r
for _ in range(IN()):
	print(f())


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	string = input()
	if string[0] == '0':
		count = 0
		maxlen = 0
		for nums in range(1, length):
			if string[nums] == '1':
				count += 1
			else:
				maxlen = max(maxlen, count)
				count = 0
		maxlen = max(maxlen, count)
	else:
		count1 = count2 = 0
		maxlen = 0
		nums = 0
		while nums < length:
			if string[nums] == '0':
				break
			count1 += 1
			nums += 1
		while nums < length:
			if string[nums] == '1':
				count2 += 1
			else:
				maxlen = max(maxlen, count2)
				count2 = 0
			nums += 1
		maxlen = max(maxlen, count2)
		maxlen += count1
	print(maxlen)


t = int(input())
for t in range(0, t):
	n = int(input())
	s = input()
	s = s + '0'
	l = []
	z = 0
	x = 0
	for i in range(0, n + 1):
		if s[i] == '1':
			z = 1
			x += 1
		else:
			if z:
				l.append(x)
			x = 0
			z = 0
	if len(l) == 0:
		print(0)
	elif len(l) == 1:
		print(l[0])
	elif s[0] == '0':
		mx = max(l)
		print(mx)
	else:
		f = l[0]
		l.pop(0)
		mx = max(l)
		print(f + mx)


for _ in range(int(input())):
	n = int(input())
	a = [*input()]
	k = [-1]
	for i in range(n):
		if a[i] == '0':
			k.append(i)
	if a[-1] == '1':
		k.append(n)
	maxi = 0
	for i in range(1, len(k) - 1):
		if k[i + 1] - k[i] - 1 > maxi:
			maxi = k[i + 1] - k[i] - 1
	if a[0] == '0':
		if k[1] - k[0] - 1 > maxi:
			print(k[1] - k[0] - 1)
		else:
			print(maxi)
	else:
		print(k[1] - k[0] - 1 + maxi)


for _ in range(int(input())):
	n = int(input())
	a = [*input()]
	flag = True
	count1 = []
	count = 0
	for i in a:
		if i == '1':
			count += 1
			flag = True
		elif flag == True:
			count1.append(count)
			flag = False
			count = 0
		else:
			continue
	if count != 0:
		count1.append(count)
	if a[0] == '0':
		print(max(count1))
	elif len(count1) <= 1:
		if len(count1) == 0:
			print(n)
		else:
			print(count1[0])
	else:
		print(count1[0] + sorted(count1[1:])[-1])


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	z = s.find('0')
	if z == -1:
		print(n)
		continue
	v = s[z:]
	print(max((len(x) for x in v.split('0'))) + z)


for i in range(int(input())):
	n = int(input())
	s = input()
	firstones = 0
	for j in range(n):
		if s[j] == '0':
			break
		firstones += 1
	(ans, flag, temp) = (0, 0, 0)
	for i in range(j + 1, n):
		if s[i] == '1' and flag == 0:
			flag = 1
			temp = 0
		if s[i] == '0' and flag == 1:
			ans = max(ans, firstones + temp)
			temp = 0
			flag = 0
		if flag == 1:
			temp += 1
	print(max(ans, firstones + temp))


for T in range(int(input())):
	n = int(input())
	s = input()
	suff = [0] * n
	if s[-1] == '1':
		suff[-1] = 1
	for i in range(n - 2, -1, -1):
		if s[i] == '1':
			suff[i] = suff[i + 1] + 1
	if s[0] == '0':
		print(max(suff))
	else:
		c = 0
		for i in range(n):
			if s[i] == '1':
				c += 1
			else:
				break
		ans = c
		for i in range(c, n):
			ans = max(ans, c + suff[i])
		print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	k = 0
	while k < n and s[k] != '0':
		k += 1
	ms = 0
	c = 0
	for i in range(k + 1, n):
		if s[i] == '1':
			c += 1
		else:
			ms = max(ms, c)
			c = 0
	ms = max(ms, c)
	print(ms + k)
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(input().split('0'))
	l1 = []
	if l[0] == '':
		print(max(l).count('1'))
	else:
		for i in l:
			if i != '':
				l1.append(i)
		if len(l1) == 0:
			print('0')
		elif len(l1) == 1:
			print(len(l[0]))
		else:
			p = l1[0]
			l1.remove(l1[0])
			print(max(l1).count('1') + p.count('1'))


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	if s == '00':
		print('0')
	elif s[0] == '1':
		temp = 0
		count = 0
		ls = []
		for i in s:
			if i == '1':
				count = count + 1
			elif i == '0':
				temp = count
				ls.append(temp)
				count = 0
		ls.append(count)
		if ls[0] == len(s):
			print(len(s))
		else:
			print(ls[0] + max(ls[1:]))
	elif s[0] == '0':
		temp = 0
		count = 0
		ls2 = []
		for i in s:
			if i == '1':
				count = count + 1
			elif i == '0':
				temp = count
				ls2.append(temp)
				count = 0
		ls2.append(count)
		if ls2[0] == len(s):
			print(len(ls2))
		else:
			print(max(ls2[1:]))
	t = t - 1


from collections import Counter
from math import log2

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	S = input()
	if S == '1' * N:
		print(N)
		continue
	if S == '0' * N:
		print(0)
		continue
	ar1 = []
	tmp = 0
	for i in range(N):
		if S[i] == '1':
			tmp += 1
		else:
			ar1.append(tmp)
			tmp = 0
	ar1.append(tmp)
	res = ar1[0] + max(ar1[1:])
	print(res)


for i in range(int(input())):
	n = input()
	a = input().split('0')
	s = 0
	if a[0]:
		s = len(a[0])
	if len(a) > 1:
		s += max(map(len, a[1:]))
	print(s)


t = int(input())
for _ in range(t):
	l = []
	n = int(input())
	s = input()
	if s[0] == '0':
		ans = 0
		i = 0
		while i < n:
			c = 0
			while i < n and s[i] == '1':
				c += 1
				i += 1
			ans = max(ans, c)
			i += 1
		print(ans)
	else:
		ans = 0
		i = 0
		p = 0
		while i < n:
			c = 0
			while i < n and s[i] == '1':
				c += 1
				i += 1
			if p == 0:
				p = c
			else:
				ans = max(ans, c)
			i += 1
		print(p + ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	L = 0
	while L < n and s[L] == '1':
		L += 1
	R = L + 1
	mx = cur = 0
	while R < n:
		if s[R] == '0':
			mx = max(mx, cur)
			cur = 0
		else:
			cur += 1
		R += 1
	mx = max(mx, cur)
	print(mx + L)


for _ in range(int(input())):
	n = int(input())
	s = input()
	suf = [0] * n
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			suf[i] = 1 + (suf[i + 1] if i + 1 < n else 0)
	ans = suf[0]
	first = -1
	for i in range(n):
		if s[i] == '0':
			first = 1
		if first != -1:
			ans = max(ans, (suf[i + 1] if i + 1 < n else 0) + suf[0])
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input()))
	ind = 0
	while ind < n and l[ind]:
		ind += 1
	if ind == n:
		print(n)
	elif ind == 0:
		maxx = 0
		count = 0
		for j in range(1, n):
			if l[j]:
				count += 1
			else:
				if maxx < count:
					maxx = count
				count = 0
		print(max(maxx, count))
	else:
		maxx = 0
		count = 0
		for j in range(ind + 1, n):
			if l[j]:
				count += 1
			else:
				if maxx < count:
					maxx = count
				count = 0
		print(ind + max(maxx, count))


def m(str):
	(mx, lg) = (0, 0)
	for i in range(len(str)):
		if str[i] == '1':
			lg += 1
			if mx < lg:
				mx = lg
		if str[i] == '0':
			lg = 0
	return mx
for i in range(int(input())):
	l = int(input())
	s = input()
	if s[0] == '0':
		print(m(s))
	else:
		(l1, z) = (0, 0)
		while s[z] == '1':
			l1 += 1
			z += 1
			if z == l - 1:
				break
		l2 = 0
		if l2 != '':
			l2 = m(s[z:])
		print(l1 + l2)


for _ in range(int(input())):
	n = int(input())
	l = []
	a = list(map(int, input()))
	c = d = 0
	for i in a:
		if i == 1:
			c += 1
		else:
			l.append(c)
			c = 0
	l.append(c)
	if a[0] == 0:
		print(max(l))
	else:
		for i in a:
			if i == 1:
				d += 1
			else:
				break
		l.remove(l[0])
		if len(l) >= 1:
			print(d + max(l))
		else:
			print(d)


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

def li():
	return list(mi())

def si():
	return str(input())

def lsi():
	return si().strip().split(' ')

def ni():
	return int(input())
for _ in range(ni()):
	n = ni()
	s = si()
	L = 0
	while L < n and s[L] == '1':
		L += 1
	R = L + 1
	mx = cur = 0
	while R < n:
		if s[R] == '0':
			mx = max(mx, cur)
			cur = 0
		else:
			cur += 1
		R += 1
	mx = max(mx, cur)
	print(mx + L)


def longestPrefOnes(n, s):
	L = 0
	while L < n and s[L] == '1':
		L += 1
	R = L + 1
	mx = cur = 0
	while R < n:
		if s[R] == '0':
			mx = max(mx, cur)
			cur = 0
		else:
			cur += 1
		R += 1
	mx = max(mx, cur)
	return mx + L
t = int(input())
assert 1 <= t <= 1000
for _ in range(t):
	n = int(input())
	assert 2 <= n <= 2 * 10 ** 5
	s = input()
	print(longestPrefOnes(n, s))


t = int(input())
while t:
	n = int(input())
	s = input()
	spans = []
	count = 0
	for i in range(n):
		if s[i] == '1':
			count += 1
		elif count != 0:
			spans.append(count)
			count = 0
		if i == n - 1:
			if count:
				spans.append(count)
	if len(spans) == 0:
		print('0')
		t -= 1
		continue
	if s[0] == '1':
		if len(spans) > 1:
			print(spans[0] + max(spans[1:]))
		else:
			print(spans[0])
	else:
		print(max(spans))
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	temp = 0
	maxi = 0
	dum = ''
	count = 0
	val = 0
	if a[0] == '0':
		for i in a:
			if i == '1':
				temp += 1
			else:
				temp = 0
			maxi = max(maxi, temp)
	else:
		for i in a:
			if i == '1':
				temp += 1
			else:
				if count == 0:
					val = temp
					count += 1
				temp = 0
			if count == 1:
				maxi = max(maxi, temp)
		if count == 0:
			maxi = temp
		else:
			maxi = maxi + val
	print(maxi)


def findMaxString(n, s, i):
	maxS = idx = 0
	while i < n:
		if s[i] == '1':
			tempC = 0
			tempIdx = i
			while i < n and s[i] == '1':
				i += 1
			if maxS <= i - tempIdx:
				idx = tempIdx
				maxS = i - tempIdx
		else:
			i += 1
	return (maxS, idx)
for _ in range(int(input())):
	n = int(input())
	s = input()
	(maxS, idx) = findMaxString(n, s, 0)
	if s[0] == '0':
		print(maxS)
	elif idx == 0:
		i = tempIdx = count = 0
		while i < n and s[i] != '0':
			i += 1
		(count, idx) = findMaxString(n, s, i)
		print(maxS + count)
	else:
		i = count = 0
		while i < n and s[i] == '1':
			i += 1
			count += 1
		print(maxS + count)


for s in [*open(0)][2::2]:
	s = s[:-1] + '0'
	l = [*map(len, s.split('0'))]
	print(max(l[1:]) + l[0])


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	m = 0
	z = 0
	p = 0
	for i in range(n):
		if s[i] == '1':
			c = c + 1
		elif s[i] == '0':
			m = i
			break
	for i in range(i + 1, n):
		if s[i] == '1':
			z = z + 1
		else:
			p = max(p, z)
			z = 0
	p = max(z, p)
	print(c + p)


for j in range(int(input())):
	n = int(input())
	s = input()
	ones = 0
	i = 0
	while i < n and s[i] == '1':
		ones += 1
		i += 1
	i += 1
	maxi = -1
	count = 0
	while i < n:
		if s[i] == '1':
			count += 1
		else:
			maxi = max(count, maxi)
			count = 0
		i += 1
	maxi = max(count, maxi)
	print(ones + maxi)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = []
	count = 0
	i = 0
	while i < n:
		if s[i] == '0':
			while i < n and s[i] == '0':
				count -= 1
				i += 1
			c.append(count)
			count = 0
		if i < n:
			if s[i] == '1':
				while i < n and s[i] == '1':
					count += 1
					i += 1
			c.append(count)
			count = 0
	if len(c) == 1:
		print(max(0, c[0]))
	elif c[0] < 0:
		print(max(c))
	else:
		m = max(c[1:])
		if m > 0:
			print(c[0] + m)
		else:
			print(c[0])


t = int(input())
for _ in range(t):
	n = int(input())
	str1 = input()
	mainList = list(str1)
	counts1 = []
	if mainList[0] == '0':
		counter = 0
		flag = 0
		for i in range(1, n):
			if mainList[i] == '1':
				flag = 1
				counter += 1
			elif flag == 1:
				flag = 0
				counts1.append(counter)
				counter = 0
		counts1.append(counter)
		counts1.sort()
		print(counts1[-1])
	else:
		counter = 0
		flag = 0
		initial1count = 0
		firstzero = 0
		for i in range(n):
			if mainList[i] == '1':
				counter += 1
			else:
				initial1count = counter
				firstzero = i
				counter = 0
				break
		for j in range(firstzero, n):
			if mainList[j] == '1':
				flag = 1
				counter += 1
			elif flag == 1:
				flag = 0
				counts1.append(counter)
				counter = 0
		counts1.append(counter)
		counts1.sort()
		if firstzero == 0:
			print(n)
		else:
			print(counts1[-1] + initial1count)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	l1 = []
	cnt = 0
	for j in range(n):
		if s[j] == '0':
			l1.append(cnt)
			cnt = 0
		elif s[j] == '1':
			cnt += 1
	l1.append(cnt)
	if s[0] == '0':
		print(max(l1))
	else:
		a = l1[0]
		l1.pop(0)
		if len(l1) > 0:
			print(a + max(l1))
		else:
			print(a)


def longestPrefOnes(n, s):
	conc_ones = []
	curr = 0
	for i in range(n):
		if s[i] == '1':
			curr += 1
		else:
			if curr:
				conc_ones.append(curr)
			curr = 0
	if curr > 0:
		conc_ones.append(curr)
	if not conc_ones:
		return 0
	if s[0] == '0':
		return max(conc_ones)
	elif len(conc_ones) <= 2:
		return sum(conc_ones)
	else:
		return conc_ones[0] + max(conc_ones[1:])
t = int(input())
assert 1 <= t <= 1000
for _ in range(t):
	n = int(input())
	assert 2 <= n <= 2 * 10 ** 5
	s = input()
	print(longestPrefOnes(n, s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	pref = 0
	ct = 0
	while ct < n and s[ct] == '1':
		ct += 1
		pref += 1
	maxi = 0
	while ct < n:
		count = 0
		while ct < n and s[ct] == '1':
			count += 1
			ct += 1
		if count > maxi:
			maxi = count
		ct += 1
	print(maxi + pref)


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	j = 0
	cnt = 0
	while j < n and s[j] != '0':
		cnt += 1
		j += 1
	c = 0
	a = 0
	for i in range(j + 1, n):
		if s[i] == '0':
			c = 0
		else:
			c += 1
			a = max(a, c)
	print(a + cnt)


def Solve(s, n):
	(cnt, start_one, max_one) = (0, 0, 0)
	b = s[0] == '1'
	for i in range(n):
		if s[i] == '1':
			cnt += 1
		else:
			if b:
				start_one = cnt
				b = False
			else:
				max_one = max(max_one, cnt)
			cnt = 0
	if b:
		start_one = cnt
	else:
		max_one = max(max_one, cnt)
	return max_one + start_one
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(Solve(s, n))


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	(j, c) = (0, 0)
	while j < n and s[j] != '0':
		c += 1
		j += 1
	curr = 0
	ans = 0
	for i in range(j + 1, n):
		if s[i] == '0':
			curr = 0
		else:
			curr += 1
			ans = max(ans, curr)
	print(ans + c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	fd = s.find('0')
	if fd == -1:
		print(len(s))
	else:
		tm = s[fd:]
		print(max((len(st) for st in tm.split('0'))) + fd)


for _ in range(int(input())):
	int(input())
	s = str(input())
	if s.count('0') == 0:
		print(len(s))
	else:
		z = s.index('0')
		l = s[z:]
		l = l.split('0')
		print(max((len(x) for x in l)) + z)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	lst = s.split('0')
	lst1 = lst[1:]
	lst1.sort()
	if len(lst) == 1:
		print(len(lst[0]))
	else:
		print(len(lst1[-1]) + len(lst[0]))