Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

There are N chairs placed in circular order. Some of the chairs are empty while others have a child sitting in it. You are required to change the places of the children so that all the children sit next to each other (i.e. they form a connected segment). You can do that by doing the following operation a number of times:

Choose a child and tell him to walk around the circle in clockwise order or anti-clockwise order until he finds the first empty chair, and tell him to sit there.

What is the minimum number of operations required to make all children sit next to each other?

------ Input ------ 

The first line contains T, the number of test-cases.

The first line of each test-case contains N, the number of chairs.

The second line of each test-case contains a binary string of length N. If the i-th character is 1 then the i-th chair has a child initially. Otherwise (i.e. the i-th character is 0) it's empty.

------ Output ------ 

For each test case, output a single line containing a single integer donating minimum number of operations needed.

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

$1 ≤ T ≤ 5,000$
$1 ≤ sum of N in all test-cases ≤ 10^{6}$
$at least one chair will be occupied$

----- Sample Input 1 ------ 
1
8
10001010
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
The initial configuration is:
       
1
0    0
1          0
0    0
1

We can tell the child who is boldened to move counter-clockwise, and the new configuration will be:
       
0
1    0
1          0
0    0
1

because he has moved to the first empty chair on his way.

Now, we again tell him to move counter-clockwise, and now the new configuration will be:
       
0
0    0
1          0
1    0
1

because he moved counter-clockwise, found an occupied chair, and hence kept moving. The next chair was vacant, and he sat down there.

Note that, in this example, we moved the same child twice, but this need not be the case. We can move different children in different moves.

You can check that this is the best we can do, and 2 is the minimum.

Difficulty: HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = input()
	s2 = 2 * s
	k = 0
	m = 0
	while k < n:
		if s2[k] == '0':
			e = k
			while e < 2 * n and s2[e] == '0':
				e += 1
			l = e - k
			if l > m:
				m = l
			k = e
		else:
			k += 1
	c = 0
	for j in range(n):
		if s[j] == '0':
			c += 1
	ans.append(c - m)
print(*ans)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	S = input()
	s = S + S
	start = 0
	maxlen = 0
	while start < N:
		if s[start] == '0':
			end = start
			while end < 2 * N and s[end] == '0':
				end += 1
			l = end - start
			if l > maxlen:
				maxlen = l
			start = end
		else:
			start += 1
	count = 0
	for i in range(N):
		if S[i] == '0':
			count += 1
	ans.append(count - maxlen)
for i in ans:
	print(i)


t = int(input())
for m in range(t):
	n = int(input())
	sit = input()
	num0 = 0
	total = 0
	max0 = 0
	s = 0
	e = 0
	i = 0
	while i < n:
		num0 = 0
		while i < n and sit[i] == '0':
			i += 1
			num0 += 1
		total += num0
		if num0 > max0:
			max0 = num0
		if num0 == i:
			s = num0
		if i == n:
			e = num0
		i += 1
	if s + e > max0:
		max0 = s + e
	print(total - max0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	totalZero = 0
	maxZero = 0
	first = 0
	last = 0
	i = 0
	while i < n:
		count = 0
		while i < n and s[i] == '0':
			i += 1
			count += 1
		totalZero += count
		if count > maxZero:
			maxZero = count
		if count == i:
			first = count
		if i == n:
			last = count
		i += 1
	if first + last > maxZero:
		maxZero = first + last
	print(totalZero - maxZero)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	i = s.find('1')
	s = s[i:] + s[:i]
	o = s.split('1')
	result = sum(map(len, o)) - max(map(len, o))
	print(result)


import sys
t = int(input())
while t:
	n = int(input())
	a = input()
	p = [0 for i in range(n)]
	s = [0 for i in range(n)]
	p[0] = int(a[0])
	s[n - 1] = int(a[n - 1])
	pos = []
	for i in range(n):
		if a[i] == '1':
			pos.append(i)
	for i in range(1, n):
		p[i] = p[i - 1] + int(a[i])
	for i in range(n - 2, -1, -1):
		s[i] = s[i + 1] + int(a[i])
	if p[n - 1] == 1:
		sys.stdout.write('0\n')
	else:
		m = n
		for i in range(1, len(pos)):
			m = min(m, n - pos[i] + pos[i - 1] + 1 - (p[pos[i - 1]] + s[pos[i]]))
		x = pos[-1] - pos[0] + 1
		if pos[0] == 0:
			x -= p[pos[-1]]
		else:
			x -= p[pos[-1]] - p[pos[0] - 1]
		m = min(m, x)
		sys.stdout.write(str(m) + '\n')
	t -= 1


from sys import stdin, stdout, exit

def listInput():
	return list(map(int, stdin.readline().split()))

def printBS(li):
	n = len(li)
	for i in range(n - 1):
		stdout.write('%d ' % li[i])
	if n != 0:
		stdout.write('%d\n' % li[n - 1])

def sin():
	return stdin.readline().rstrip()

def inp():
	return int(stdin.readline())
cases = inp()
for _ in range(cases):
	n = inp()
	s = sin()
	m = 0
	c = 0
	for i in s:
		if i == '1':
			m = max(m, c)
			c = 0
		else:
			c += 1
	m = max(m, c)
	c = 0
	for i in s:
		if i == '0':
			c += 1
		else:
			break
	else:
		c = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			c += 1
		else:
			break
	m = max(c, m)
	print(s.count('0') - m)


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	total = 0
	l = s.index('1')
	r = s.rindex('1')
	for i in range(n):
		if s[i] == '0':
			total += 1
	s = s + s[:l + 1]
	count = 0
	max1 = 0
	for i in range(len(s) - 1):
		if s[i] == '0' and s[i + 1] == '0':
			count += 1
		elif s[i] == '0' and s[i + 1] == '1':
			count += 1
			if count > max1:
				max1 = count
			count = 0
	print(total - max1)


for _ in range(int(input())):
	n = int(input())
	a = input()
	i = 0
	start = 0
	end = 0
	c = 0
	z = 1
	t = 0
	while i < n:
		if int(a[i]) == 0:
			c += 1
			t += 1
		else:
			z = max(z, t)
			t = 0
		i += 1
	i = 0
	while i < n and int(a[i]) == 0:
		start += 1
		i += 1
	i = n - 1
	while i >= 0 and int(a[i]) == 0:
		end += 1
		i -= 1
	z = max(z, end + start)
	if c > 0:
		print(c - z)
	else:
		print('0')


import io
import sys

def test_data():
	return io.StringIO('3\n8\n10001010\n11\n10010001001\n15\n00010010001001\n')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			n = int(next(lines))
			chairs = next(lines).strip()
			yield (chairs,)

def calc(chairs):
	tmp_chairs = chairs.lstrip('0')
	chairs = tmp_chairs + '0' * (len(chairs) - len(tmp_chairs))
	chairs = chairs.rstrip('1')
	empties = 0
	distances = []
	for chair in chairs:
		if chair == '1':
			if empties != 0:
				distances.append(empties)
				empties = 0
		else:
			empties += 1
	if empties != 0:
		distances.append(empties)
	return sum(sorted(distances)[:-1])

def calc_derp(chairs):
	first = chairs[0]
	prev = first
	movements = 0
	for chair in chairs[1:]:
		if prev == chair:
			continue
		elif chair == '1':
			movements += 1
		prev = chair
	if first == prev and first == '1':
		movements = max(movements - 1, 0)
	return movements
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


for t in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	while i < len(s) and s[i] == '0':
		i += 1
	s = s[i:] + s[:i]
	s = s.split('1')
	z = sum((len(p) for p in s))
	m = max((len(p) for p in s))
	print(z - m)