Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Teams $A$ and $B$ are having a penalty shoot-out to decide the winner of their football match. Each team gets to take a shot $N$ times, and the team with the higher number of scored goals at the end wins. If the number of goals scored during the shoot-out by each team turns out to be the same even after all $2N$ shots, then they stop and agree that the result is a draw.

The two teams take shots alternately — team $A$ shoots first, then team $B$ shoots, then team $A$ and so on until team $B$ takes its $N$-th shot (at which point each team has taken exactly $N$ shots). Even though all $2N$ shots are taken, the result of the shoot-out is often known earlier — e.g. if team $A$ has already scored $N-1$ goals and team $B$ has missed at least two shots, team $A$ is definitely the winner.

For each shot, you know whether it was a goal or a miss. You need to find the earliest moment when the winner is known — the smallest $s$ ($0 ≤ s ≤ 2N$) such that after $s$ shots, the result of the shoot-out (whether team $A$ won, team $B$ won or the match is drawn) would be known even if we did not know the results of the remaining $2N-s$ shots.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains a string $S$ with length $2 \cdot N$, where for each valid $i$, the $i$-th character is '0' if the $i$-th shot was a miss or '1' if it was a goal.

------  Output ------
For each test case, print a single line containing one integer — the smallest $s$ such that after $s$ shots, the result of the shoot-out is known.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ contains only characters '0' and '1'
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2

3

101011

3

100001
----- Sample Output 1 ------ 
4

6
----- explanation 1 ------ 
Example case 1: After four shots, team $A$ has scored $2$ goals and team $B$ has scored $0$ goals. Whatever happens afterwards, team $A$ is guaranteed to win, since even if team $B$ scored their last (and only) goal and team $A$ did not score their last goal, team $A$ would still win by $1$ goal.

Example case 2: Team $A$ scores the first goal and after that, neither team scores any goals until the last shot. Up till then, there is always a possibility that the match could end in a draw if team $B$ scored a goal with its last shot, or in the victory of team $A$ if it was a miss. We can only guarantee the result after the last shot.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
def score(s, i):
	if i == '1':
		return s + 1
	else:
		return s
t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	a = 0
	b = 0
	for i in range(2 * n):
		if i % 2 == 1:
			b = score(b, s[i])
			if b + (n - (i + 1) // 2) < a or a + (n - (i + 1) // 2) < b:
				print(i + 1)
				break
		elif i % 2 == 0:
			a = score(a, s[i])
			if a + (2 * n - i - 1) // 2 < b or b + ((2 * n - i - 1) // 2 + 1) < a:
				print(i + 1)
				break
		if i == 2 * n - 1:
			print(i + 1)


for z in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	b = 0
	ra = n
	rb = n
	for i in range(2 * n):
		if i % 2 == 0:
			a += int(s[i])
			ra -= 1
		else:
			b += int(s[i])
			rb -= 1
		if a > b + rb or b > a + ra or (ra == 0 and rb == 0):
			print(i + 1)
			break


for _ in range(int(input())):
	n = int(input())
	s = input()
	(c1, c2, c3, c4, f) = (0, 0, n, n, 0)
	for i in range(n):
		if s[2 * i] == '1':
			c1 += 1
		c3 -= 1
		if c1 - c2 > c4 or c2 - c1 > c3:
			print(2 * i + 1)
			f = 1
			break
		if s[2 * i + 1] == '1':
			c2 += 1
		c4 -= 1
		if c2 - c1 > c3 or c1 - c2 > c4:
			print(2 * i + 2)
			f = 1
			break
	if f == 0:
		print(2 * n)


T = int(input())
while T > 0:
	N = int(input())
	s = input()
	d = 0
	ans = 2 * N
	for i in range(2 * N):
		if i % 2 == 0:
			d += int(s[i])
			if d > 0:
				if d > N - i / 2:
					ans = i + 1
					break
			elif -d > N - 1 - i / 2:
				ans = i + 1
				break
		else:
			d -= int(s[i])
			if abs(d) > N - 1 - int(i / 2):
				ans = i + 1
				break
	print(ans)
	T -= 1


import math
mod = 10 ** 9 + 7

def findans(n, s):
	l = 2 * n
	tag = 1
	cnta = 0
	cntb = 0
	for i in range(0, l):
		if s[i] == '1':
			if tag == 1:
				cnta += 1
			else:
				cntb += 1
		if tag == 1:
			add = (l - i - 1) // 2
			add += 1
			if cnta > cntb + add:
				return i + 1
			if cntb > cnta + add - 1:
				return i + 1
		else:
			add = (l - i - 1) // 2
			if cntb > cnta + add:
				return i + 1
			if cnta > cntb + add:
				return i + 1
		tag ^= 1
	return l

def main():
	t = int(input())
	ans = []
	while t != 0:
		t -= 1
		n = int(input())
		s = input()
		val = findans(n, s)
		ans.append(val)
	for i in range(len(ans)):
		print(ans[i])
main()


import sys
sys.setrecursionlimit(10 ** 5)

def pro(arr):
	n = len(arr)
	for i in range(n):
		arr[i] = int(arr[i])
	(c1, c2) = (n // 2, n // 2)
	c1 -= 1
	c2 -= 1
	b = 1 if arr[1] else 0
	a = 1 if arr[0] else 0
	result = 0
	if a > b:
		result = 1
	if a < b:
		result = 2
	for i in range(2, n):
		if i % 2:
			if arr[i]:
				b += 1
			c2 -= 1
		else:
			a += 1 if arr[i] else 0
			c1 -= 1
		if a > b + c2:
			break
		if a + c1 < b:
			break
	print(i + 1)
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(input())
	pro(arr)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	Aw = N + 1
	Bw = N + 1
	Ag = 0
	Bg = 0
	flag = 0
	for i in range(len(S)):
		if i % 2 == 0:
			if S[i] == '0':
				Bw -= 1
			else:
				Ag += 1
		elif S[i] == '0':
			Aw -= 1
		else:
			Bg += 1
		if Aw == Ag or Bw == Bg:
			print(i + 1)
			flag = 1
			break
	if flag == 0:
		print(2 * N)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = n * 2
	a = 0
	b = 0
	left_a = n
	left_b = n
	for i in range(len(s)):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		if i % 2 == 0:
			left_a -= 1
		else:
			left_b -= 1
		if a > b + left_b:
			ans = i + 1
			break
		elif b > a + left_a:
			ans = i + 1
			break
	print(ans)


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

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

def getvals():
	while True:
		yield from input().split()

def shot(s):
	yield from s

def score_round(s):
	return int(s == '1')

def solve(*args):
	(n, s) = args
	score = [0, 0]
	result = shot(s)
	for i in range(1, n + 1):
		for turn in [0, 1]:
			score[turn] += score_round(next(result))
			if score[0] + (n - i) < score[1] or score[1] + (n - i + 1 - turn) < score[0]:
				return 2 * i + turn - 1
	return 2 * n

def do_codechef():
	for t in rii():
		n = ii()
		s = si()
		print(solve(n, s))
do_codechef()
exit()


t = int(input())
for i in range(t):
	n = int(input())
	l = 2 * n
	p = input()
	a = 0
	b = 0
	c = n
	d = n
	ans = l
	for j in range(l):
		if p[j] == '1':
			if j % 2 == 0:
				a += 1
			else:
				b += 1
		if j % 2 == 0:
			c -= 1
		else:
			d -= 1
		if a > b + d:
			ans = j + 1
			break
		if b > a + c:
			ans = j + 1
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	length = 2 * n
	penalty = input()
	currScore_A = 0
	currScore_B = 0
	lefShot_A = n
	leftShot_B = n
	winVar = length
	for index in range(length):
		if penalty[index] == '1':
			if index % 2 == 0:
				currScore_A += 1
			else:
				currScore_B += 1
		if index % 2 == 0:
			lefShot_A -= 1
		else:
			leftShot_B -= 1
		if currScore_A > currScore_B + leftShot_B:
			winVar = index + 1
			break
		if currScore_B > currScore_A + lefShot_A:
			winVar = index + 1
			break
	print(winVar)


from math import ceil as c
t = int(input())
while t != 0:
	n = int(input())
	s = input()[:2 * n]
	(a_left, b_left) = (n, n)
	(a, b) = (0, 0)
	ans = 2 * n
	for i in range(2 * n):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		if i % 2 == 0:
			a_left -= 1
		else:
			b_left -= 1
		if a > b + b_left:
			ans = i + 1
			break
		if b > a + a_left:
			ans = i + 1
			break
	print(ans)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	my_string = input()
	a = 0
	a_n = N
	b_n = N
	b = 0
	for i in range(len(my_string)):
		if i % 2 == 0:
			if my_string[i] == '1':
				a += 1
				a_n -= 1
			else:
				a_n -= 1
		elif my_string[i] == '1':
			b += 1
			b_n -= 1
		else:
			b_n -= 1
		if a > b + b_n:
			print(i + 1)
			break
		elif b > a + a_n:
			print(i + 1)
			break
		elif a == b and i == len(my_string) - 1:
			print(i + 1)
			break


for _ in range(int(input())):
	v = int(input())
	d = input()
	(p, q, r, s) = (0, 0, 0, 0)
	k = 0
	for i in range(2 * v):
		if d[i] == '1':
			if i % 2 == 0:
				p += 1
			else:
				q += 1
		elif i % 2 == 0:
			r += 1
		else:
			s += 1
		if p > v - s or q > v - +r:
			k = 1
			break
	if k:
		print(i + 1)
	else:
		print(2 * v)


for i in range(int(input())):
	n = int(input())
	(a, b) = (0, 0)
	(ac, bc) = (0, 0)
	s = input()
	flag = -1
	for i in range(2 * n):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		if i % 2 == 0:
			ac += 1
		else:
			bc += 1
		if b + n - bc < a or a + n - ac < b:
			print(i + 1)
			flag = 0
			break
	if flag == -1:
		print(2 * n)


try:
	p = int(input())
	for j in range(p):
		v = int(input())
		d = input()
		(p, q, r, s) = (0, 0, 0, 0)
		k = 0
		for i in range(2 * v):
			if d[i] == '1':
				if i % 2 == 0:
					p += 1
				else:
					q += 1
			elif i % 2 == 0:
				r += 1
			else:
				s += 1
			if p > v - s or q > v - r:
				k = 1
				break
		if k:
			print(i + 1)
		else:
			print(2 * v)
except EOFError:
	pass


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	a = []
	b = []
	r = 0
	(c1, c2) = (0, 0)
	(c3, c4) = (0, 0)
	for i in range(2 * n):
		if i % 2 == 0:
			a.append(s[i])
			if s[i] == '1':
				c1 += 1
			else:
				c3 += 1
		else:
			b.append(s[i])
			if s[i] == '1':
				c2 += 1
			else:
				c4 += 1
		if n - (c2 + c4) < c1 - c2 or n - (c1 + c3) < c2 - c1:
			r = i + 1
			break
	if r > 0:
		print(r)
	else:
		print(2 * n)


z = int(input())
for j in range(z):
	v = int(input())
	d = input()
	(z, q, r, s) = (0, 0, 0, 0)
	k = 0
	for i in range(2 * v):
		if d[i] == '1':
			if i % 2 == 0:
				z += 1
			else:
				q += 1
		elif i % 2 == 0:
			r += 1
		else:
			s += 1
		if z > v - s or q > v - r:
			k = 1
			break
	if k:
		print(i + 1)
	else:
		print(2 * v)


for _ in range(int(input())):
	g = int(input())
	s = input()
	(a, b, am, bm) = (0, 0, 0, 0)
	f = 0
	for i in range(2 * g):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		elif i % 2 == 0:
			am += 1
		else:
			bm += 1
		if a > g - bm or b > g - am:
			f = 1
			break
	if f:
		print(i + 1)
	else:
		print(2 * g)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(a_hit, b_hit, a_miss, b_miss) = (0, 0, 0, 0)
	c = 0
	if len(s) == 2:
		print(2)
	else:
		for i in range(2 * n - 1):
			if s[i] == '1':
				if i % 2 == 0:
					a_hit += 1
				else:
					b_hit += 1
			elif i % 2 == 0:
				a_miss += 1
			else:
				b_miss += 1
			if a_hit > n - b_miss or b_hit > n - a_miss:
				c = 1
				break
		if c == 0:
			print(2 * n)
		else:
			print(i + 1)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	a = 0
	b = 0
	am = 0
	bm = 0
	ar = n
	br = n
	for i in range(0, 2 * n):
		if i % 2 == 0:
			if s[i] == '1':
				a += int(s[i])
			else:
				am += 1
			ar -= 1
		else:
			if s[i] == '1':
				b += int(s[i])
			else:
				bm += 1
			br -= 1
		if a > b + br or b > a + ar:
			break
	print(i + 1)


p = int(input())
for i in range(p):
	n = int(input())
	(at, bt, a_s, bs, ans) = (n, n, 0, 0, 0)
	s = input()
	for i in range(len(s)):
		k = int(s[i])
		if i % 2 != 0:
			bs = bs + k
			bt -= 1
		elif i % 2 == 0:
			a_s = a_s + k
			at -= 1
		a = a_s
		b = bs
		if a > b and a - b > bt:
			print(i + 1)
			ans = 1
			break
		elif b > a and b - a > at:
			print(i + 1)
			ans = 1
			break
	if ans == 0:
		print(2 * n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	b = 0
	a1 = 0
	b1 = 0
	flag = 0
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == '1':
				a += 1
			else:
				a1 += 1
		elif s[i] == '1':
			b += 1
		else:
			b1 += 1
		rema = n - a1
		remb = n - b1
		if b > rema or a > remb:
			flag = 1
			print(i + 1)
			break
	if flag == 0:
		print(len(s))


t = int(input())
for x in range(t):
	p = int(input())
	s = input()
	(a, b, am, bm) = (0, 0, 0, 0)
	f = 0
	for i in range(2 * p):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		elif i % 2 == 0:
			am += 1
		else:
			bm += 1
		if a > p - bm or b > p - am:
			f = 1
			break
	if f:
		print(i + 1)
	else:
		print(2 * p)


for I in range(int(input())):
	n = int(input())
	s = input()
	(a, b) = (0, 0)
	(a1, b1) = (n, n)
	k = 2 * n
	for i in range(k):
		if i % 2 == 0:
			if s[i] == '1':
				a = a + 1
			else:
				a1 = a1 - 1
		elif s[i] == '1':
			b = b + 1
		else:
			b1 = b1 - 1
		if a > b1:
			print(i + 1)
			break
		elif b > a1:
			print(i + 1)
			break
		if i == k - 1:
			print(k)


for _ in range(int(input())):
	n = int(input())
	g = input()
	ans = len(g)
	(a, b) = (0, 0)
	(c, d) = (n, n)
	for i in range(len(g)):
		if i % 2 == 0:
			if g[i] == '1':
				a += 1
			c -= 1
		else:
			if g[i] == '1':
				b += 1
			d -= 1
		if a > b + d:
			ans = i + 1
			break
		elif b > a + c:
			ans = i + 1
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = b = h = j = 0
	f = 0
	c = 0
	for i in range(2 * n):
		c += 1
		if i % 2 == 0:
			a = a + int(s[i])
			h = h + 1
		else:
			b = b + int(s[i])
			j = j + 1
		if b + (n - j) < a:
			break
		elif n - h + a < b:
			break
	print(c)


for j in range(int(input())):
	num = int(input())
	(at, bt, a_s, bs, res) = (num, num, 0, 0, 0)
	s = input()
	for i in range(len(s)):
		k = int(s[i])
		if i % 2 != 0:
			bs = bs + k
			bt -= 1
		elif i % 2 == 0:
			a_s = a_s + k
			at -= 1
		a = a_s
		b = bs
		if a > b and a - b > bt:
			print(i + 1)
			res = 1
			break
		elif b > a and b - a > at:
			print(i + 1)
			res = 1
			break
	if res == 0:
		print(2 * num)


t = int(input())
while t:
	n = int(input())
	s = input()
	a1 = 0
	b = 0
	c = 0
	d = 0
	g = 0
	for i in range(2 * n):
		if s[i] == '1':
			if i % 2 == 0:
				a1 = a1 + 1
			else:
				b = b + 1
		elif i % 2 == 0:
			c = c + 1
		else:
			d = d + 1
		if a1 > n - d or b > n - c:
			g = 1
			break
	if g == 1:
		print(i + 1)
	else:
		print(2 * n)
	t = t - 1


x = int(input())
for j in range(x):
	t = int(input())
	d = input()
	(p, q, r, s) = (0, 0, 0, 0)
	k = 0
	for i in range(2 * t):
		if d[i] == '1':
			if i % 2 == 0:
				p += 1
			else:
				q += 1
		elif i % 2 == 0:
			r += 1
		else:
			s += 1
		if p > t - s or q > t - r:
			k = 1
			break
	if k:
		print(i + 1)
	else:
		print(2 * t)


from math import ceil

def answer():
	(a, b) = (0, 0)
	for i in range(n):
		if i & 1 == 0 and s[i] == '1':
			a += 1
		if i & 1 and s[i] == '1':
			b += 1
		(v1, v2) = (n - i - 1, n - i - 2)
		if a > b + ceil(v1 / 2):
			return i + 1
		if b > a + ceil(v2 / 2):
			return i + 1
	return n
for T in range(int(input())):
	n = int(input())
	n *= 2
	s = input()
	print(answer())


t = int(input())
for k in range(t):
	n = int(input())
	a = input()
	res = 2 * n
	f = s = 0
	c = d = n
	for i in range(len(a)):
		if i % 2 == 0:
			if a[i] == '1':
				f += 1
			c -= 1
		else:
			if a[i] == '1':
				s += 1
			d -= 1
		if f > s + d:
			res = i + 1
			break
		elif s > f + c:
			res = i + 1
			break
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = 2 * n
	(a, b) = (0, 0)
	(c, p) = (n, n)
	for i in range(k):
		if i % 2 == 0:
			if s[i] == '1':
				a = a + 1
			else:
				c = c - 1
		elif s[i] == '1':
			b = b + 1
		else:
			p = p - 1
		if a > p:
			print(i + 1)
			break
		elif b > c:
			print(i + 1)
			break
		if i == k - 1:
			print(k)


t = int(input())
for i in range(t):
	turns = int(input())
	aturns = turns
	bturns = turns
	ascore = 0
	bscore = 0
	flag = 0
	s = input()
	for i in range(len(s)):
		k = int(s[i])
		if i % 2 != 0:
			bscore = bscore + k
			bturns -= 1
		elif i % 2 == 0:
			ascore = ascore + k
			aturns -= 1
		a = ascore
		b = bscore
		if a > b and a - b > bturns:
			print(i + 1)
			flag = 1
			break
		elif b > a and b - a > aturns:
			print(i + 1)
			flag = 1
			break
	if flag == 0:
		print(2 * turns)


for _ in range(int(input())):
	n = int(input())
	s = input()
	sa = 0
	sb = 0
	f = 100
	if n == 1:
		f = 7
		print('2')
	else:
		i = 0
		j = 1
		for k in range(n):
			wa = 0
			wb = 0
			if s[i] == '1':
				sa += 1
			baki = n - k - 1
			bakj = n - k
			if sa + baki > sb + bakj:
				wa += 1
			elif sa + baki < sb + bakj:
				wb += 1
			if sa + baki > sb:
				wa += 1
			elif sa + baki < sb:
				wb += 1
			if sa > sb + bakj:
				wa += 1
			elif sa < sb + bakj:
				wb += 1
			if wa == 3 or wb == 3:
				print(i + 1)
				f = 7
				break
			if wa != 3 and wb != 3:
				wa = 0
				wb = 0
				if s[j] == '1':
					sb += 1
				baki = n - k - 1
				bakj = n - k - 1
				if sa + baki > sb + bakj:
					wa += 1
				elif sa + baki < sb + bakj:
					wb += 1
				if sa + baki > sb:
					wa += 1
				elif sa + baki < sb:
					wb += 1
				if sa > sb + bakj:
					wa += 1
				elif sa < sb + bakj:
					wb += 1
				if wa == 3 or wb == 3:
					print(j + 1)
					f = 7
					break
			i += 2
			j += 2
	if f != 7:
		print(n * 2)


try:
	t = int(input())
	for i in range(0, t):
		n = int(input())
		s = input()
		(a, b) = (0, 0)
		(lefta, leftb) = (n, n)
		for i in range(0, len(s)):
			if i % 2 == 0:
				lefta -= 1
			if i % 2 == 1:
				leftb -= 1
			if s[i] == '1':
				if i % 2 == 0:
					a += 1
				else:
					b += 1
			if a > b + leftb:
				print(i + 1)
				break
			if b > a + lefta:
				print(i + 1)
				break
			if a == b and leftb == 0:
				print(i + 1)
				break
except:
	pass


for _ in range(0, int(input())):
	x = int(input())
	fo = input()
	count = a = b = aa = bb = flag = 0
	while count < 2 * x:
		if count % 2 == 0:
			if fo[count] == '1':
				a += 1
			else:
				aa += 1
		elif fo[count] == '1':
			b += 1
		else:
			bb += 1
		if x - bb < a and a >= b or (x - aa < b and a <= b):
			flag = 1
			break
		count += 1
	if flag == 1:
		print(count + 1)
	else:
		print(count)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	a = 0
	b = 0
	ans = 2 * n
	for i in range(0, 2 * n):
		if i % 2 == 0:
			if s[i] == '1':
				a += 1
			if a > b:
				if n - i // 2 + b < a:
					ans = i + 1
					break
			if b > a:
				if n - (i + 2) // 2 + a < b:
					ans = i + 1
					break
		else:
			if s[i] == '1':
				b += 1
			if a > b:
				if n - (i + 1) // 2 + b < a:
					ans = i + 1
					break
			if b > a:
				if n - (i + 1) // 2 + a < b:
					ans = i + 1
					break
	print(ans)


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		sp = 0
		ga = 0
		gb = 0
		ca = n
		cb = n
		for i in range(2 * n):
			if sp == 0:
				sp = 1
				if s[i] == '1':
					ga += 1
				else:
					ga += 0
				ca -= 1
			elif sp == 1:
				sp = 0
				if s[i] == '1':
					gb += 1
				else:
					gb += 0
				cb -= 1
			if ga > gb + cb:
				print(i + 1, end='\n')
				break
			elif gb > ga + ca:
				print(i + 1, end='\n')
				break
			elif ga == gb and i == 2 * n - 1:
				print(i + 1, end='\n')
				break
except EOFError as e:
	print(end='')


def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		(c_a, c_b, r_a, r_b) = (0, 0, n, n)
		for i in range(2 * n):
			if i % 2 == 0:
				if s[i] == '1':
					c_a += 1
				r_a -= 1
			if i % 2 == 1:
				if s[i] == '1':
					c_b += 1
				r_b -= 1
			if c_a - c_b > r_b:
				break
			if c_b - c_a > r_a:
				break
		print(i + 1)
solve()


for j in range(int(input())):
	n = int(input())
	g = input()
	(sum1, sum2) = (0, 0)
	(chance1, chance2) = (n, n)
	for i in range(n * 2):
		if i % 2 == 0:
			chance1 -= 1
			if g[i] == '1':
				sum1 += 1
		else:
			chance2 -= 1
			if g[i] == '1':
				sum2 += 1
		if sum1 > sum2 + chance2 or sum2 > sum1 + chance1:
			print(i + 1)
			break
		elif sum1 == sum2 and chance1 == 0 and (chance2 == 0):
			print(2 * n)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a_score = b_score = 0
	a_rem = b_rem = n
	i = 0
	flag = False
	while i < len(s):
		if i % 2 == 0:
			if s[i] == '1':
				a_score += 1
			a_rem -= 1
		else:
			if s[i] == '1':
				b_score += 1
			b_rem -= 1
		if a_score > b_score + b_rem or b_score > a_score + a_rem:
			print(i + 1)
			flag = True
			break
		i += 1
	if not flag:
		print(2 * n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a_hit = 0
	a_miss = 0
	b_hit = 0
	b_miss = 0
	even = n
	odd = n
	flag = 0
	for i in range(2 * n):
		if i % 2 == 0:
			even -= 1
			if s[i] == '1':
				a_hit += 1
			else:
				a_miss += 1
		else:
			odd -= 1
			if s[i] == '1':
				b_hit += 1
			else:
				b_miss += 1
		if a_hit > b_hit and a_hit - b_hit > odd:
			flag = 1
			print(i + 1)
			break
		if b_hit > a_hit and b_hit - a_hit > even:
			flag = 1
			print(i + 1)
			break
	if flag == 0:
		print(2 * n)


for _ in range(int(input())):
	n = int(input())
	lis = input()
	turns = 0
	a = b = am = bm = 0
	for i in range(len(lis)):
		if i % 2 == 0:
			if lis[i] == '1':
				a += 1
			else:
				am += 1
		elif lis[i] == '1':
			b += 1
		else:
			bm += 1
		if a > n - bm or b > n - am:
			print(i + 1)
			break
	else:
		print(2 * n)


for t in range(int(input())):
	n = int(input())
	s = input()
	(a, b, a_miss, b_miss) = (0, 0, 0, 0)
	flag = 0
	for i in range(2 * n):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		elif i % 2 == 0:
			a_miss += 1
		else:
			b_miss += 1
		if a > n - b_miss or b > n - a_miss:
			flag = 1
			break
	if flag == 0:
		print(2 * n)
	else:
		print(i + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = b = am = bm = 0
	for j in range(len(s)):
		if j % 2 == 0:
			if s[j] == '1':
				a += 1
			else:
				am += 1
		elif s[j] == '1':
			b += 1
		else:
			bm += 1
		if a > n - bm or b > n - am:
			print(j + 1)
			break
	else:
		print(2 * n)


def pen():
	ts = int(input())
	tots = map(int, input())
	(ta, tb, sa, sb) = (0, 0, 0, 0)
	for _ in tots:
		if ta == tb:
			sa += _
			ta += 1
		else:
			sb += _
			tb += 1
		la = sa + ts - ta
		lb = sb + ts - tb
		if sa > lb or sb > la:
			break
	print(ta + tb)
for x in range(int(input())):
	pen()


def PENALTY():
	team_shoot = int(input())
	total_shoot = map(int, input())
	(t_A, t_B, s_A, s_B) = (0, 0, 0, 0)
	for i in total_shoot:
		if t_A == t_B:
			s_A += i
			t_A += 1
		else:
			s_B += i
			t_B += 1
		l_A = s_A + team_shoot - t_A
		l_B = s_B + team_shoot - t_B
		if s_A > l_B or s_B > l_A:
			break
	print(t_A + t_B)
testCase = int(input())
for x in range(testCase):
	PENALTY()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 2 * n
	(a, b) = (0, 0)
	for i in range(2 * n):
		if i % 2 == 0:
			if s[i] == '1':
				a = a + 1
			if a > b:
				diff = a - b
				if diff > math.ceil((2 * n - i - 1) / 2):
					ans = i + 1
					break
			elif b > a:
				diff = b - a
				if diff > (2 * n - i - 1) // 2:
					ans = i + 1
					break
		else:
			if s[i] == '1':
				b = b + 1
			if a > b:
				diff = a - b
				if diff > (2 * n - i - 1) // 2:
					ans = i + 1
					break
			elif b > a:
				diff = b - a
				if diff > (2 * n - i - 1) // 2:
					ans = i + 1
					break
	print(ans)


for T in range(int(input())):
	n = int(input())
	s = input()
	score_a = 0
	score_b = 0
	S = 2 * n
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == '1':
				score_a += 1
			diff = score_b - score_a
			if diff > 0 and diff > n - (i + 2) // 2 or (diff < 0 and -diff > n - (i + 1) // 2):
				S = i + 1
				break
		elif i % 2:
			if s[i] == '1':
				score_b += 1
			diff = abs(score_a - score_b)
			if diff > n - (i + 1) // 2:
				S = i + 1
				break
	print(S)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(a, b) = (0, 0)
	(al, bl) = (n, n)
	cnt = 0
	for i in range(2 * n):
		if i % 2 == 0:
			if s[i] == '1':
				a += 1
			al -= 1
		else:
			if s[i] == '1':
				b += 1
			bl -= 1
		if a > b + bl or b > a + al:
			print(i + 1)
			break
		elif al == bl and al == 0:
			print(n * 2)


x = int(input())
t = [0] * x
for _ in range(x):
	n = int(input())
	s = input()
	(a, b, am, bm) = (0, 0, 0, 0)
	flag = 0
	for i in range(2 * n):
		if s[i] == '1':
			if i % 2 == 0:
				a += 1
			else:
				b += 1
		elif i % 2 == 0:
			am += 1
		else:
			bm += 1
		if a > n - bm or b > n - am:
			t[_] = i + 1
			flag = 1
			print(i + 1)
			break
	if flag == 0:
		t[_] = 2 * n
		print(2 * n)


t = int(input())
for j in range(t):
	n = int(input())
	s = list(input())
	anum = 0
	bnum = 0
	aleft = n
	bleft = n
	ans = 2 * n
	a = []
	b = []
	for i in range(2 * n):
		if i % 2 == 0:
			if s[i] == '1':
				anum = anum + 1
			aleft -= 1
		else:
			if s[i] == '1':
				bnum = bnum + 1
			bleft -= 1
		if anum > bnum + bleft:
			ans = i + 1
			break
		elif bnum > anum + aleft:
			ans = i + 1
			break
	print(ans)


t = int(input())
while t:
	n = int(input())
	s = input()
	(a1, a0, b1, b0) = (0, 0, 0, 0)
	i = 0
	while i < 2 * n:
		if i % 2 == 0:
			if s[i] == '1':
				a1 += 1
			else:
				a0 += 1
		elif s[i] == '1':
			b1 += 1
		else:
			b0 += 1
		if a0 + b1 > n or a1 + b0 > n or i + 1 == 2 * n:
			break
		i += 1
	print(i + 1)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(2)
	else:
		c1 = 0
		c11 = 0
		c2 = 0
		c22 = 0
		ca = 0
		for i in range(len(s)):
			if i == len(s) - 1:
				print(len(s))
				break
			if i % 2 == 0:
				if s[i] == '1':
					c1 += 1
					if c11 + n - c1 - c11 < c22:
						print(i + 1)
						break
					elif c11 + n - c1 - c11 == c22:
						for i in range(i + 1, 2 * n, 2):
							if s[i] == '1':
								ca += 1
				elif s[i] == '0':
					c11 += 1
					if c22 + n - c2 - c22 < c11:
						print(i + 1)
						break
			elif i % 2 != 0:
				if s[i] == '1':
					c2 += 1
					if c22 + n - c2 - c22 < c11:
						print(i + 1)
						break
				elif s[i] == '0':
					c22 += 1
					if c11 + n - c1 - c11 < c22:
						print(i + 1)
						break