You have a binary string S. You can perform the following operation on S:
Select any substring S_{L \dots R} (1 ≤ L ≤ R ≤ |S|) which is sorted in non-decreasing order and remove it from S.
(Both the left and right halves are concatenated after performing the operation)

For e.g. if S = 100011000, we can perform the following operation: 100\underline{011}000 \rightarrow 100000

Find the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the length of the binary string S.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

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

For each test case, output the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

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

$1 ≤ T ≤ 10^{5}$
$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 ------ 
3
3
000
5
01110
2
10

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

----- explanation 1 ------ 
Test case $1$: The binary string is already sorted, so we need no operations.

Test case $2$: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string $00$ is sorted.

Test case $3$: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string $1$ is sorted.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	c = s.count('10')
	print(c)


T = int(input())
while T:
	T = T - 1
	N = int(input())
	S = input()
	count = 0
	for i in range(1, N):
		if S[i] == '0' and S[i - 1] == '1':
			count += 1
	print(count)


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


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	print(s.count('10'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	print(s.count('10'))


for _ in range(int(input())):
	n = int(input())
	x = input()
	c = 0
	for i in range(1, n):
		if x[i - 1] == '1' and x[i] == '0':
			c = c + 1
	print(c)


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	c = 0
	for i in range(1, n):
		if s[i] == '0' and s[i - 1] == '1':
			c = c + 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	for i in range(1, n):
		if s[i - 1] == '1' and s[i] == '0':
			cnt += 1
	print(cnt)


def solve():
	n = int(input())
	s = input()
	count = 0
	for i in range(n - 1):
		if s[i] > s[i + 1]:
			count += 1
	print(count)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for j in range(n - 1):
		if s[j] == '1' and s[j + 1] == '0':
			count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 0
	for j in range(n - 1):
		if s[j] == '1' and s[j + 1] == '0':
			count += 1
	print(count)


for _ in range(int(input())):
	N = int(input())
	S = input().strip()
	print(S.count('10'))


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	print(string.count('10'))


T = int(input())
for tc in range(T):
	n = int(input())
	s = input()
	count = 0
	print(s.count('10'))


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '0':
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(len(s) - 1):
		if s[i:i + 2] == '10':
			c += 1
	print(c)


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


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	s += '7'
	(z, o) = (0, 0)
	for i in range(n):
		if n - 1 == i and s[i] == '1':
			break
		if s[i] != s[i + 1] and s[i] == '0':
			z += 1
		elif s[i] != s[i + 1] and s[i] == '1':
			o += 1
	print(min(o, z))


for _ in range(int(input())):
	n = int(input())
	a = input()
	pre = '0'
	co = 0
	for i in range(len(a)):
		if a[i] == '0' and i - 1 >= 0:
			if a[i - 1] == '1':
				co += 1
	print(co)


for _ in range(int(input())):
	a = input()
	l = input().strip()
	print(l.count('10'))


for _ in range(int(input())):
	N = int(input())
	X = input().strip()
	print(X.count('10'))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	print(a.count('10'))


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	if n == 1:
		print(0)
	else:
		ones = s.split('0')
		ocount = len([o for o in ones if len(o) > 0])
		if ocount == 0:
			print(0)
		elif s[-1] == '1':
			print(ocount - 1)
		else:
			print(ocount)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = s.find('1')
	if p > 0:
		s = s[p:]
	s = s[::-1]
	p = s.find('0')
	if p > 0:
		s = s[p:]
	flip = [0, 0]
	flip[ord(s[0]) - 48] += 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			flip[ord(s[i]) - 48] += 1
	print(min(flip))


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	count = 0
	for i in range(n - 1):
		if a[i] == '1' and a[i + 1] == '0':
			count = count + 1
	print(count)


for _ in range(int(input())):
	size = int(input())
	st = input()
	res = 0
	i = 0
	while i < len(st) - 1:
		if st[i] == '1' and st[i + 1] == '0':
			res += 1
		i += 1
	print(res)


T = int(input())
for i in range(0, T):
	N = int(input())
	S = input()
	ops = 0
	for j in range(0, N - 1):
		num = j
		if S[j] == '1':
			if S[j + 1] == '0':
				for k in range(1, N):
					if j - k < 0:
						break
					if S[j - k] == '1':
						num = num - 1
					else:
						break
				ops = ops + 1
	print(ops)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	s = input()
	stack = []
	for i in s:
		if len(stack) == 0 or stack[-1] != i:
			stack.append(i)
	s = ''.join(stack)
	n = len(s)
	zc = s.count('0')
	oc = 0
	ans = math.inf
	for i in range(n):
		ans = min(ans, oc + zc)
		if s[i] == '0':
			zc -= 1
		else:
			oc += 1
	ans = min(ans, oc + zc)
	print(ans)
for t in range(int(input())):
	solve()


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	wq = deque(s)
	fl = 0
	c = 0
	while len(wq) > 0:
		a = wq.popleft()
		if a == '1':
			fl = 1
		if a == '0' and fl == 1:
			c += 1
			fl = 0
	print(c)


from collections import deque
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	s = str(input())
	wq = deque(s)
	fl = 0
	c = 0
	while len(wq) > 0:
		a = wq.popleft()
		if a == '1':
			fl = 1
		if a == '0' and fl == 1:
			c += 1
			fl = 0
	print(c)


n = input()
val = []
for i in range(int(n) * 2):
	val.append(input())
for i in range(len(val)):
	if i % 2 != 0:
		xc = val[i]
		res = 0
		for k in range(1, len(xc)):
			if xc[k] == '0' and xc[k - 1] == '1':
				res += 1
		print(res)


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	pre = s[0]
	ans = 0
	for i in s:
		if int(pre) > int(i):
			ans += 1
		pre = i
	print(ans)


def sorted_substring(n, s):
	a = 0
	b = 0
	for i in range(n):
		if s[i] == '1':
			a = 1
		elif a != 0 and s[i] == '0':
			b += 1
			a = 0
	if s[n - 1] == '1' and a == 0:
		print(b - 1)
	else:
		print(b)
t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	sorted_substring(n, s)


t = int(input())
for _ in range(t):
	N = int(input())
	S = input()
	ans = 0
	for i in range(N - 1):
		if S[i + 1] == '0' and S[i] == '1':
			ans = ans + 1
	print(ans)


n = int(input())
for i in range(0, n):
	count = 0
	c = int(input())
	d = input()
	for j in range(1, c):
		if d[j - 1] > d[j]:
			count = count + 1
	print(count)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	i = 0
	sortexist = 0
	while i < n - 1:
		if s[i] == '1' and s[i + 1] == '0':
			sortexist += 1
		i += 1
	print(sortexist)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(s.count('10'))


from collections import Counter, UserString

def decimal(n):
	return int(ans) + int(int(ans) != ans)
ynO = 'Yes'

def yn(check='o', caps=False):
	if check == 'o':
		return ynO
	elif check == 1:
		ynO = 'Yes'
	elif check == 0:
		ynO = 'No'
	else:
		raise ValueError('Numbers others than 1 and 0 do not come into consideration')
	if caps:
		ynO = ynO.upper()

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
mod = lambda n: n % (10 ** 9 + 7)
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	lenOfBinStr = ii()
	binStr = si()
	ans = binStr.count('10')
	print(ans)


num = int(input())
for _ in range(num):
	n = int(input())
	val = input()
	print(val.count('10'))


for x in range(int(input())):
	n = int(input())
	s = input()
	print(s.count('10'))


for _ in range(int(input())):
	n = int(input())
	a = input()
	print(a.count('10'))


T = int(input())
for _ in range(T):
	N = int(input())
	arr = input()
	print(arr.count('10'))


T = int(input())
for _ in range(T):
	N = int(input())
	arr = input()
	subrays = 0
	current = arr[0]
	for i in arr[1:]:
		if i < current:
			subrays += 1
		current = i
	print(subrays)


T = int(input())
for j in range(T):
	N = int(input())
	S = input()
	c = 0
	for i in range(N - 1):
		if S[i] == '1' and S[i + 1] == '0':
			c += 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	S = input()
	n = 0
	for i in range(N - 1):
		if S[i] == '1' and S[i + 1] == '0':
			n += 1
	print(n)


n = int(input())
for i in range(n):
	n = int(input())
	s = input()
	c = 0
	i = 0
	while i < n:
		if s[i] == '1':
			c += 1
			while i < n and s[i] == '1':
				i += 1
		i += 1
	if s[-1] == '1':
		c -= 1
	print(c)


for i in range(int(input())):
	num = int(input())
	data = input()
	n = 0
	for i in range(num - 1):
		if data[i] == '1' and data[i + 1] == '0':
			n += 1
	print(n)


for num_case in range(int(input())):
	digit_num = int(input())
	data = input()
	num = 0
	for i in range(digit_num - 1):
		if data[i] == '1' and data[i + 1] == '0':
			num += 1
	print(num)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	N = inp()
	ans.append(insr().count('10'))
outplt(ans)


n = int(input())
for _ in range(n):
	l = int(input())
	b = input()
	count = 0
	for i in range(l - 1):
		if b[i] == '1' and b[i + 1] == '0':
			count += 1
	print(count)


import re
for _ in range(int(input())):
	_ = input()
	s = input()
	print(len(re.findall('10', s)))


for i in range(int(input())):
	l = int(input())
	s = input()[:l]
	z = list(s)
	c = 0
	for j in range(len(z) - 1):
		if z[j] == '1' and z[j + 1] == '0':
			c += 1
	print(c)


for _ in range(int(input())):
	input()
	print(input().count('10'))


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	c = 0
	i = 0
	while i < n - 1:
		if s[i] + s[i + 1] == '10':
			c += 1
		i += 1
	print(c)
	t -= 1


T = int(input())
for tc in range(T):
	n = int(input())
	s = input()
	no = 0
	for i in range(0, len(s) - 1):
		if s[i] > s[i + 1]:
			no += 1
	print(no)


T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	no = 0
	for i in range(0, len(S) - 1):
		if S[i] > S[i + 1]:
			no += 1
	print(no)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	first_one = s[i]
	ans = 0
	while i < n - 1:
		entered_flag = 0
		if int(s[i]) > int(s[i + 1]):
			i = i + 1
			while s[i] == 1 and i < n:
				i = i + 1
			entered_flag = 1
		if entered_flag == 0:
			i = i + 1
		else:
			ans = ans + 1
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	string = input()
	c = 0
	for j in range(len(string) - 1):
		if string[j] > string[j + 1]:
			c += 1
	print(c)