From an array A containing N integers, you construct a binary string S of length (N - 1) as follows. For all 1 ≤ i < N:
If A_{i} < A_{i+1}, then S_{i} = 0.
If A_{i} > A_{i+1}, then S_{i} = 1.

Given the string S, determine the count of indices i (1 ≤ i ≤ N) such that it is possible for A_{i} to be the maximum element of the array A.

------ 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 size of the array A.
- The second line of each test case contains the binary string S of length (N - 1) containing 0s and 1s only.

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

For each test case, output the count of indices i (1 ≤ i ≤ N) such that it is possible for A_{i} to be the maximum element of the array A.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
3
2
0
7
000111
6
11100

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

----- explanation 1 ------ 
Test case $1$: Here $A_{1} < A_{2}$. Therefore clearly only $A_{2}$ can be the maximum element of $A$.

Test case $2$: Here $A_{1} < A_{2}$, $A_{2} < A_{3}$, $A_{3} < A_{4}$, $A_{4} > A_{5}$, $A_{5} > A_{6}$ and $A_{6} > A_{7}$. Therefore, clearly only $A_{4}$ can be the maximum element of $A$.

Test case $3$: Here $A_{1} > A_{2}$, $A_{2} > A_{3}$, $A_{3} > A_{4}$, $A_{4} < A_{5}$ and $A_{5} < A_{6}$. Therefore $A_{1}$ and $A_{6}$ both can be the maximum elements of $A$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	lent = int(input())
	arr1 = [int(x) for x in list(input())]
	count = 0
	if lent == 2:
		print(1)
		continue
	if lent == 3:
		if arr1 == [1, 1]:
			print(1)
		elif arr1 == [1, 0]:
			print(2)
		elif arr1 == [0, 1]:
			print(1)
		elif arr1 == [0, 0]:
			print(1)
		continue
	if lent == 4:
		if arr1 == [1, 1, 1] or arr1 == [0, 1, 1] or arr1 == [0, 0, 1] or (arr1 == [0, 0, 0]):
			print(1)
		else:
			print(2)
		continue
	if arr1[0] == 1:
		count += 1
	if arr1[-1] == 0:
		count += 1
	for y in range(lent - 2):
		if arr1[y] == 0 and arr1[y + 1] == 1:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ns = ''
	current = ''
	for i in s:
		if current != i:
			ns += i
			current = i
	if ns == '0' or ns == '1':
		print(1)
	else:
		internalmaxnodes = ns.count('01')
		if len(ns) > 1 and ns[0] == '1':
			internalmaxnodes += 1
		if len(ns) > 1 and ns[-1] == '0':
			internalmaxnodes += 1
		print(internalmaxnodes)


for t in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	c = 0
	for i in range(len(l) - 1):
		if l[i] == '0':
			continue
		else:
			if l[i + 1] != '1':
				c += 1
			continue
	c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = [999] * n
	for i in range(n):
		if i < len(s):
			if s[i] == '0':
				a[i] = a[i] - 1
			else:
				a[i + 1] = a[i] - 1
	a.sort(reverse=True)
	print(a.count(a[0]))


tests = int(input())
for i in range(tests):
	num = int(input())
	s = input()
	if num == 2:
		print(1)
	else:
		count = s.count('01')
		if s[0] == '1':
			count += 1
		if s[-1] == '0':
			count += 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 2:
		print(1)
	else:
		count = s.count('01')
		if s[0] == '1':
			count += 1
		if s[-1] == '0':
			count += 1
		print(count)


for x in range(int(input())):
	n = int(input())
	num = input()
	if n == 2:
		print(1)
	else:
		c = num.count('01')
		if num[0] == '1':
			c += 1
		if num[-1] == '0':
			c += 1
		print(c)


for t in range(int(input())):
	N = int(input())
	S = input()
	if N == 2:
		print(1)
	else:
		ans = S.count('01')
		if S[0] == '1':
			ans += 1
		if S[-1] == '0':
			ans += 1
		print(ans)


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


for i in range(int(input())):
	a = input()
	b = input()
	pre = 0
	count = 0
	for i in b:
		if int(i) > pre:
			count += 1
		pre = int(i)
	if pre == 0:
		count += 1
	print(count)


tests = int(input())
for test in range(tests):
	number = input()
	my_list = input()
	previous = 0
	count = 0
	for i in my_list:
		if int(i) > previous:
			count += 1
		previous = int(i)
	if previous == 0:
		count += 1
	print(count)


testcases = int(input())
i = 0
while i < testcases:
	n = int(input())
	s = input()
	new = []
	new.append(s[0])
	for l in s:
		if l != new[-1]:
			new.append(l)
	x = 0
	for l in range(len(new)):
		if new[l] == '1':
			x = x + 1
			continue
		if l == len(new) - 1:
			if new[l] == '0':
				x = x + 1
	print(x)
	i = i + 1


def HMM(N, s):
	if N == 2:
		return '1'
	else:
		ans = s.count('01')
		if s[0] == '1':
			ans += 1
		if s[-1] == '0':
			ans += 1
		return ans
for i in range(int(input())):
	N = int(input())
	s = input()
	print(HMM(N, s))


for _ in range(int(input())):
	N = int(input())
	s = input()
	if N == 2:
		print('1')
	else:
		ans = s.count('01')
		if s[0] == '1':
			ans += 1
		if s[-1] == '0':
			ans += 1
		print(ans)


def m(s):
	if len(s) == 1:
		return 1
	c = 1
	for i in range(len(s) - 1):
		if s[i:i + 2] == [1, 0]:
			c += 1
	return c
for i in range(int(input())):
	n = int(input())
	print(m(list(map(int, [*input()]))))


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


for _ in range(int(input())):
	k = int(input())
	s = input()
	l = [0] * k
	for i in range(len(s)):
		if s[i] == '0':
			l[i] -= 1
		else:
			l[i + 1] -= 1
	print(l.count(0))


for _ in range(int(input())):
	n = int(input())
	arr = input()
	cnt = 0
	if len(arr) == 1:
		print('1')
	else:
		cnt += arr.count('01')
		if arr[0] == '1':
			cnt += 1
		if arr[n - 2] == '0':
			cnt += 1
		print(cnt)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ma = 0
	if s[0] == '1':
		ma += 1
	if s[-1] == '0':
		ma += 1
	k = s.count('01')
	print(ma + k)


for _ in range(int(input())):
	N = int(input())
	S = f'0{input()}1'
	print(S.count('01'))


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	s = input()
	count = 0
	prev = s[0]
	flag = 0
	if N == 2 or N == 1:
		print(1)
		continue
	for i in range(1, N - 1):
		if prev == '0' and s[i] == '1':
			count += 1
		prev = s[i]
	if s[0] == '1':
		count += 1
	if s[-1] == '0':
		count += 1
	print(count)


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


for z in range(int(input())):
	n = int(input())
	str = input()
	count = 1
	for i in range(len(str) - 1):
		if str[i] + str[i + 1] == '10':
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	if s[0] == '1':
		c = c + 1
	if s[-1] == '0':
		c = c + 1
	p = s.count('01')
	print(c + p)


for i in range(int(input())):
	a = int(input())
	b = input()
	count = 0
	temp = 0
	d = 0
	for j in b:
		if j == '0':
			if d == 0:
				temp += count
				count = 0
				d += 1
		elif j == '1':
			if count == 0:
				count += 1
				d = 0
	print(temp + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()[:n - 1]
	c = 0
	k = s.count('01')
	if n == 2:
		print(1)
	else:
		if s[0] == '1':
			c += 1
		if s[-1] == '0':
			c += 1
		print(k + c)


for i in range(0, int(input())):
	a = int(input())
	b = input()
	count = 1
	for j in range(0, len(b) - 1):
		if b[j + 1] == '0' and b[j] == '1':
			count = count + 1
	print(count)


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


t = int(input())
while t:
	n = int(input())
	stri = input()
	count = int(0)
	if stri[0] == '1':
		count += 1
	if stri[n - 2] == '0':
		count += 1
	for i in range(1, n - 1):
		if stri[i] == '1' and stri[i - 1] == '0':
			count += 1
	print(count)
	t = t - 1


for i in range(int(input())):
	N = int(input())
	S = input()
	maximas = 0
	if S[-1] == '0':
		maximas += 1
	if S[0] == '1':
		maximas += 1
	maximas += S.count('01')
	print(maximas)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	if n == 2:
		print(1)
	else:
		c = s.count('01')
		if s[0] == '1':
			c += 1
		if s[-1] == '0':
			c += 1
		print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = 0
	if n == 2:
		print(1)
	else:
		x = s.count('01')
		ans = ans + x
		if s[0] == '1':
			ans = ans + 1
		if s[-1] == '0':
			ans = ans + 1
		print(ans)


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


t = int(input())
i = 0
ans = 0
while i < t:
	one = 0
	zero = 0
	n = int(input())
	s = input()
	if n == 2:
		print(1)
	else:
		ans = s.count('01')
		if s[0] == '1':
			ans += 1
		if s[-1] == '0':
			ans += 1
		print(ans)
	i += 1


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


t = int(input())
for i in range(t):
	x = int(input())
	y = input()
	count = 0
	zz = y.count('10')
	print(zz + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	p = 0
	if s[0] == '1':
		p += 1
	if s[-1] == '0':
		p += 1
	k = s.count('01')
	p += k
	print(p)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	incr_count = 0
	decr_count = 0
	for i in range(len(s) - 1):
		if s[i] > s[i + 1]:
			decr_count += 1
		elif s[i] < s[i + 1]:
			incr_count += 1
	if len(s) == 1:
		print(1)
	elif incr_count > decr_count:
		print(incr_count)
	else:
		print(decr_count + 1)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline()
	if n == 2:
		print(1)
	else:
		arr = [0] * n
		ans = 0
		for i in range(n - 1):
			if s[i] == '0':
				arr[i + 1] = arr[i] + 1
			elif s[i] == '1':
				arr[i + 1] = arr[i] - 1
		for i in range(1, n - 1):
			if arr[i] > arr[i + 1] and arr[i - 1] < arr[i]:
				ans += 1
		if arr[0] > arr[1]:
			ans += 1
		if arr[-1] > arr[-2]:
			ans += 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	str1 = input()
	ans = 0
	if str1[0] == '1':
		ans += 1
	if str1[-1] == '0':
		ans += 1
	res = str1.count('01')
	ans += res
	print(ans)


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


for i in range(int(input())):
	n = int(input())
	k = input()
	if len(k) == 1:
		print(1)
	else:
		m = k.count('01')
		if k[0] == '1':
			m += 1
		if k[-1] == '0':
			m += 1
		print(m)


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	count = 0
	count_10 = A.count('10')
	print(count_10 + 1)


for i in range(int(input())):
	n = int(input())
	a = str(input())
	if a[0] == '1':
		sum = 1
	else:
		sum = 0
	for j in range(n - 2):
		if a[j] == '0' and a[j + 1] == '1':
			sum += 1
	if a[n - 2] == '0':
		sum += 1
	print(sum)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	b = 0
	c = 1
	for i in s:
		a = int(i)
		if a < b:
			c += 1
		b = a
	print(c)


for i in range(int(input())):
	length = int(input())
	string = input()
	total = string.count('01')
	if string[-1] == '0':
		total += 1
	if string[0] == '1':
		total += 1
	print(total)


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


t = int(input())
for tc in range(t):
	l = int(input())
	s = input()
	ones = s.count('1')
	zeros = s.count('0')
	count = s.count('01')
	if s[0] == '1':
		count += 1
	if s[l - 2] == '0':
		count += 1
	print(count)


import sys
input = sys.stdin.readline

def gcd(a, b):
	while b != 0:
		temp = b
		b = a % b
		a = temp
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		bns = input().strip()
		c = 0
		for i in range(n - 2):
			if bns[i] == '0' and bns[i + 1] == '1':
				c += 1
		if bns[0] == '1':
			c += 1
		if bns[n - 2] == '0':
			c += 1
		print(c)
main()