You are given a binary string S of length N. You are allowed to perform the following types of operations on string S:
Delete any one character from S, and concatenate the remaining parts of the string. For example, if we delete the third character of S = 1101, it becomes S = 111.
Flip all the characters of S. For example, if we flip all character of S = 1101, it becomes S = 0010.

Given that you can use either type of operation any number of times, find the minimum number of operations required to make all characters of the string S equal to 0.

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

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

For each test case, output on a new line, the minimum number of operations required to make all characters of the string S equal to 0.

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

$1 ≤ T ≤ 2000$
$1 ≤ N ≤ 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 ------ 
4
2
01
3
101
3
111
4
0000

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

----- explanation 1 ------ 
Test case $1$: You can use one operation to delete the second character of the string $S$. Thus, the string becomes $0$. Note that all characters of this string are $0$ and thus, it satisfies the conditions.

Test case $2$: You can perform the following operations:
- Operation $1$: Flip all characters of the string. Thus, string becomes $010$.
- Operation $2$: Delete the second character of the string. Thus, string becomes $00$.

Note that we have obtained a string having all characters as $0$ in two operations. It can be shown that this is the minimum number of operations required.

Test case $3$: You can use one operation to flip all characters of the string $S$. Thus, the string becomes $000$. Note that all characters of this string are $0$ and thus, it satisfies the conditions.

Test case $4$: The existing string satisfies the conditions. Thus, we require zero operations.

Difficulty: EASY

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	s = input()
	cnt1 = s.count('1')
	cnt0 = s.count('0')
	if cnt0 >= cnt1:
		val = cnt1
	else:
		val = 1 + cnt0
	print(val)


for i in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeroes = s.count('0')
	c = 0
	if zeroes >= ones:
		c = c + ones
	else:
		c = c + (1 + zeroes)
	print(c)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	c_1 = s.count('1')
	c_0 = s.count('0')
	if c_0 >= c_1:
		print(c_1)
	else:
		print(c_0 + 1)


for _ in range(int(input())):
	N = int(input())
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if zero >= one:
		val = one
	else:
		val = 1 + zero
	print(val)


for _ in range(int(input())):
	(n, s) = (int(input()), [int(i) for i in input()])
	(cnz, cno, cnf) = (0, 0, 0)
	for i in s:
		if i == 0:
			cnz += 1
		else:
			cno += 1
	if cno == 0:
		cnf = 0
	elif cnz == 0:
		cnf = 1
	elif cno > cnz:
		cnf += 1
		cnf += cnz
	else:
		cnf += cno
	print(cnf)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	numOfZeros = 0
	numOfOnes = 0
	for i in range(n):
		if s[i] == '0':
			numOfZeros += 1
		else:
			numOfOnes += 1
	if numOfOnes == 0:
		print(0)
	elif numOfZeros == 0:
		print(1)
	elif numOfOnes > numOfZeros:
		print(numOfZeros + 1)
	else:
		print(numOfOnes)


for _ in range(int(input())):
	n = int(input())
	string = input()
	one = string.count('1')
	zero = string.count('0')
	if zero >= one:
		val = one
	else:
		val = 1 + zero
	print(val)


n = int(input())
for i in range(n):
	a = int(input())
	s = input()
	o = s.count('1')
	z = s.count('0')
	if z >= o:
		b = o
		val = o
	else:
		val = 1 + z
	print(val)


t = int(input())
while t > 0:
	a = int(input())
	st = input()
	one = 0
	zero = 0
	for i in range(0, a):
		if st[i] == '0':
			zero += 1
		else:
			one += 1
	if zero == a:
		print('0')
	elif one == a:
		print('1')
	elif one > zero:
		print(zero + 1)
	else:
		print(one)
	t -= 1


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


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


T = int(input())
for i in range(T):
	N = int(input())
	S = str(input())
	A = 0
	B = 0
	for i in range(N):
		if S[i] == '0':
			A += 1
		else:
			B += 1
	if A >= B:
		print(B)
	else:
		print(A + 1)


t = int(input())
for i in range(t):
	x = int(input())
	lst = list(map(int, input()))
	m = lst.count(1)
	n = lst.count(0)
	if n < m:
		print(n + 1)
	elif n == 0:
		print(1)
	else:
		print(min(m, n))


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


n = int(input())
for i in range(n):
	ln = input()
	k = input()
	os = k.count('0')
	ones = k.count('1')
	if os >= ones:
		print(ones)
	else:
		print(os + 1)


for i in range(int(input())):
	x = int(input())
	s = input()
	ans = 0
	zero = s.count('0')
	ones = s.count('1')
	if ones > zero:
		ans = zero + 1
	else:
		ans = ones
	print(ans)


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


def fun1(N):
	pass
T = int(input())
while T:
	n = int(input())
	s = input()
	ones = s.count('1')
	if ones > int(n / 2):
		print(1 + (n - ones))
	else:
		print(ones)
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	list(str(s))
	c0 = s.count('0')
	c1 = n - c0
	if c0 >= c1:
		print(c1)
	else:
		print(c0 + 1)


for z in range(int(input())):
	n = int(input())
	s = input()
	k = []
	for i in s:
		k.append(int(i))
	x = sum(k)
	if sum(k) > n / 2:
		print(n - x + 1)
	else:
		print(x)


for i in range(int(input())):
	L = int(input())
	Str = input()
	if Str.count('1') == 0:
		print(0)
	else:
		count1 = Str.count('1')
		count0 = Str.count('0')
		if count0 >= count1:
			print(L - count0)
		else:
			print(L - count1 + 1)


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


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	c = st.count('0')
	c1 = st.count('1')
	if c >= c1:
		print(c1)
	else:
		print(c + 1)


n = int(input())
for _ in range(n):
	l = int(input())
	s = input()
	ca = '1' * l
	co = '0' * l
	if ca in s:
		print('1')
	elif co in s:
		print('0')
	elif '1' in s:
		p = s.split('0')
		suma = 0
		for i in p:
			suma = len(i) + suma
		if suma > l // 2:
			paso = l - suma + 1
			print(paso)
		else:
			print(suma)
	else:
		print('error')


s = int(input())
for i in range(s):
	a = int(input())
	b = input()
	count = 0
	count1 = 0
	ans = 0
	for j in range(a):
		if b[j] == '0':
			count += 1
		elif b[j] == '1':
			count1 += 1
		if count1 > count:
			ans = count + 1
		else:
			ans = count1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().strip()))
	z = s.count(0)
	o = s.count(1)
	if z >= o:
		print(o)
	else:
		print(z + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	t = 0
	if s.count('1') > s.count('0'):
		r = ''
		for i in s:
			if i == '1':
				r += '0'
			else:
				r += '1'
		x = r.count('1')
		t += x + 1
	else:
		x = s.count('1')
		t += x
	print(t)


n = int(input())
lcases = []
for i in range(1, n + 1):
	num = int(input())
	string1 = input()
	lcases.append(string1)
for i in lcases:
	numberof0 = 0
	numberof1 = 0
	for k in i:
		if k == '0':
			numberof0 += 1
		elif k == '1':
			numberof1 += 1
	if numberof0 == numberof1:
		print(numberof1)
	elif numberof0 > numberof1:
		print(numberof1)
	elif numberof0 < numberof1:
		print(numberof0 + 1)


for t in range(int(input())):
	n = int(input())
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if zero >= one:
		val = one
	else:
		val = 1 + zero
	print(val)


for i in range(int(input())):
	a = int(input())
	b = input()
	count1 = 0
	count2 = 0
	for j in b:
		if int(j) == 1:
			count1 += 1
		else:
			count2 += 1
	if count1 > count2:
		print(count2 + 1)
	elif count1 < count2:
		print(count1)
	else:
		print(count1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	p = s.count('1')
	q = s.count('0')
	if q == p or q > p:
		print(p)
	elif q < p and p != n:
		print(q + 1)
	elif p == n:
		print('1')
	elif q == n:
		print('0')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	one_count = s.count('1')
	zero_count = s.count('0')
	if one_count == zero_count:
		print(one_count)
	elif one_count > zero_count:
		print(1 + zero_count)
	else:
		print(one_count)


for _ in range(int(input())):
	x = int(input())
	y = input()
	if y.count('0') >= y.count('1'):
		print(y.count('1'))
	else:
		print(y.count('0') + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	o = s.count('1')
	if z == o:
		print(z)
	elif z < o:
		print(z + 1)
	elif z > o:
		print(o)
	elif z == len(s):
		print(0)
	elif o == len(s):
		print(1)


t = int(input())
for i in range(t):
	n = int(input())
	x = input()
	count1 = 0
	count0 = 0
	count1 = x.count('1')
	count0 = x.count('0')
	if count0 >= count1:
		print(count1)
	else:
		print(count0 + 1)


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


def solve():
	n = int(input())
	s = input()
	(zero, one) = (s.count('0'), s.count('1'))
	print(min(zero, one) + 1 if zero < one else min(zero, one))
t = int(input())
for _ in range(t):
	solve()


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


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


t = int(input())
for i in range(t):
	n = int(input())
	k = input()
	one = k.count('1')
	zero = k.count('0')
	if zero >= one:
		print(one)
	else:
		print(zero + 1)


for i in range(int(input())):
	n = int(input())
	array = input()
	a = {'0': 0, '1': 0}
	for j in array:
		a[j] += 1
	if a['0'] >= a['1']:
		print(a['1'])
	else:
		print(a['0'] + 1)


for i in range(int(input())):
	number = int(input())
	string = input()
	zeroes = string.count('0')
	ones = string.count('1')
	print(min(ones, zeroes + 1))


for i in range(int(input())):
	n = int(input())
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	print(min(ones, zeros + 1))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	z = s.count('0')
	if z == n:
		print(0)
	else:
		o = s.count('1')
		if o == n:
			print(1)
		elif o > z:
			print(z + 1)
		else:
			print(o)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()[:n]
	s = list(s)
	if n == s.count('0'):
		print(0)
	elif n == s.count('1'):
		print(1)
	elif s.count('1') <= s.count('0'):
		print(s.count('1'))
	else:
		print(1 + s.count('0'))


def fun(s):
	if s.count('1') <= s.count('0'):
		return s.count('1')
	elif s.count('1') == len(s):
		return 1
	else:
		return s.count('0') + 1
for _ in range(int(input())):
	n = int(input())
	s = input()
	d = fun(s)
	print(d)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = a.count('0')
	c = a.count('1')
	d = 0
	if b < c:
		print(1 + b)
	else:
		print(c)


T = int(input())
for t in range(T):
	a = int(input())
	b = input()
	zero_count = b.count('0')
	one_count = b.count('1')
	if one_count == zero_count:
		print(zero_count)
	elif zero_count == a:
		print(0)
	elif one_count == a:
		print(1)
	elif one_count > zero_count:
		print(zero_count + 1)
	elif one_count < zero_count:
		print(one_count)


T = int(input())
for i in range(T):
	n = input()
	s = input()
	c0 = s.count('0')
	c1 = s.count('1')
	c = 0
	if c0 < c1:
		c = 1 + s.count('0')
	else:
		c = s.count('1')
	print(c)


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	o_count = s.count('0')
	l_count = s.count('1')
	if o_count == -1:
		print(1)
	elif l_count == -1:
		print(0)
	elif l_count > o_count:
		print(o_count + 1)
	else:
		print(l_count)


for _ in range(int(input())):
	n = int(input())
	s = [x for x in input()]
	d = {}
	d[0] = 0
	d[1] = 0
	for i in s:
		if i == '1':
			d[1] += 1
		else:
			d[0] += 1
	if len(s) == d[0]:
		print(0)
	elif len(s) == d[1]:
		print(1)
	elif d[1] > d[0]:
		print(d[0] + 1)
	elif d[1] == d[0]:
		print(d[1])
	else:
		print(d[1])


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = b.count('0')
	d = b.count('1')
	if c == d:
		print(c)
	elif c > d:
		print(d)
	else:
		print(c + 1)


for i in range(int(input())):
	n = int(input())
	s = input()[:n]
	one = s.count('1')
	zero = s.count('0')
	if zero == n:
		print('0')
	elif one == n:
		print('1')
	elif zero > one:
		print(one)
	elif one == zero:
		print(one)
	else:
		print(zero + 1)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	z = 0
	o = 0
	for i in s:
		if i == '1':
			o += 1
		else:
			z += 1
	if z == 0:
		print('1')
	elif o == 0:
		print('0')
	elif o == z:
		print(z)
	elif o < z:
		print(o)
	else:
		print(z + 1)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = str(s)
	if s1.count('0') >= s1.count('1'):
		print(s1.count('1'))
	else:
		print(s1.count('0') + 1)