Chef has a string S of length N, consisting of +, -, and 0, where + denotes a source of positive charge, - denotes a source of negative charge, and 0 denotes a neutral object.

Each second, the charge sources emit their respective charge to their immediate neighbours. The charge emissions cannot affect other charge sources but can convert a neutral object into a charge source as following:
If an object was initially neutral, and had exactly one charged source as neighbour, it becomes a charged source as received by its neighbour.
If an object was initially neutral, and had no charged source as neighbour, it remains a neutral object.
If an object was initially neutral, and had both charged sources as neighbours, it becomes a charged source as received by its neighbours. Note that in case of neighbours with opposite charges, the object remains neutral.

For example, after one second, +0+ becomes +++, 00- becomes 0--, 000 remains 000 and +0- remains +0-. Refer to samples for further explanation.

Find out the number of neutral objects in the string after infinite time. 

------ 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 number of objects.
- The next line contains a string S of length N, consisting of +, -, and 0, where + denotes a source of positive charge, - denotes a source of negative charge, and 0 denotes a neutral object.

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

For each test case, output on a new line, the number of neutral objects in the string after infinite time. 

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

$1 ≤ T ≤ 2000$
$1 ≤ N ≤ 10^{5}$
$S$ consists of +, -, and 0 only.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
00
3
-+0
6
00+-00
8
0-0+000-

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

----- explanation 1 ------ 
Test case $1$: Since there is no charge source, both neutral objects will remain neutral.

Test case $2$: After $1$ second:
- The negative source emits a negative charge, but since there is no neutral neighbour for the negative source, it has no effect.
- The positive source emits a positive charge and since the neighbour to its right is neutral, the neutral object becomes a positive source.

Thus, the string becomes -++ after one second. Note that the string will remain the same after this and thus, it has no neutral objects after infinite time.

Test case $3$:
- After $1$ second, the string is 0++--0. Note that only the immediate neutral neighbours of charge sources have been affected.
- After $2$ seconds, the string is +++---. Since all objects are now charged sources, they will remain the same now onwards.

Thus, after infinite time, the string has no neutral objects.

Test case $4$: After $1$ second, the string is --0++0--. Note that the string will remain the same now onwards.

Thus, after infinite time, the string has $2$ neutral objects.

Difficulty: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	if s == n * '0':
		print(n)
	else:
		i = 0
		ans = 0
		k = 0
		n1 = 0
		p = 0
		for i in range(n):
			if s[i] == '+':
				p = 1
				if n1 == 1:
					n1 = 0
					if k % 2 == 1:
						ans += 1
				k = 0
			elif s[i] == '-':
				n1 = 1
				if p == 1:
					p = 0
					if k % 2 == 1:
						ans += 1
				k = 0
			elif s[i] == '0':
				k += 1
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(i, j) = (0, 0)
	a = 0
	if list(s).count('0') < n:
		while j < n:
			if s[j] == '0':
				j += 1
			elif s[i] == '0' and s[j] != '0':
				i = j
				j += 1
			elif s[i] == s[j]:
				i = j
				j += 1
			else:
				if (j - i) % 2 == 0:
					a += 1
				i = j
				j += 1
	else:
		a += n
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	if a == '0' * n:
		print(n)
	elif '+' in a and '-' in a:
		l = []
		c = 0
		for j in range(n):
			if a[j] in '+-':
				if l == [] or l[0] == a[j]:
					l = [a[j], j]
				else:
					c += (j - l[1] + 1) % 2
					l = [a[j], j]
		print(c)
	else:
		print('0')


t = int(input())
for _ in range(t):
	n = int(input())
	l = input()
	ans = 0
	while '000' in l:
		l = l.replace('000', '0')
	if l == '0' or l == '00':
		print(n)
	else:
		ans += l.count('-0+')
		ans += l.count('+0-')
		print(ans)


for _ in range(int(input())):
	a = int(input())
	b = input()
	while '000' in b:
		b = b.replace('000', '0')
	if set(b) == {'0'}:
		print(a)
	else:
		c = b.count('-0+')
		d = b.count('+0-')
		print(c + d)


t = int(input())
for i in range(t):
	n = int(input())
	x = input()
	k = x.count('0')
	if k == len(x):
		print(k)
	else:
		flag = 1
		while flag == 1:
			flag = 0
			if '000' in x:
				flag = 1
				x = x.replace('000', '0')
		print(x.count('+0-') + x.count('-0+'))


for i in range(int(input())):
	num = int(input())
	string = input()
	lis = []
	symbol = []
	ans = 0
	for j in range(num):
		if string[j] == '-' or string[j] == '+':
			lis.append(j)
			symbol.append(string[j])
	if len(lis) == 0:
		print(num)
	else:
		for j in range(1, len(lis)):
			rem = lis[j] - lis[j - 1]
			if symbol[j - 1] != symbol[j] and rem % 2 == 0:
				ans += 1
		print(ans)


for T in range(int(input())):
	n = int(input())
	s = input()
	if s.count('0') == n:
		print(n)
	else:
		zc = 0
		ans = 0
		for i in range(n):
			if s[i] == '+' or s[i] == '-':
				c = s[i]
				i += 1
				while i < n and s[i] == '0':
					i += 1
					zc += 1
				if i < n and s[i] != c and (zc % 2 == 1):
					ans += 1
			zc = 0
		print(ans)


testCase = int(input())
for _ in range(testCase):
	numOfCharges = int(input())
	charges = input()
	l = list()
	flag = False
	inital = ''
	count = 0
	numOfZero = 0
	for i in charges:
		if i == '0':
			if flag:
				count += 1
		if i == '+':
			if flag:
				if i == inital:
					count = 0
				else:
					inital = i
					if count % 2 != 0:
						numOfZero += 1
						count = 0
			else:
				flag = True
				inital = i
		if i == '-':
			if flag:
				if i == inital:
					count = 0
				else:
					inital = i
					if count % 2 != 0:
						numOfZero += 1
						count = 0
			else:
				flag = True
				inital = i
	if flag is False:
		numOfZero = numOfCharges
	print(numOfZero)


for test_case in range(int(input())):
	n = int(input())
	s = input()
	prev = None
	count = 0
	res = 0
	for i in range(n):
		if s[i] == '0':
			count += 1
		else:
			if prev:
				if count:
					if prev != s[i]:
						if count % 2 != 0:
							res += 1
			count = 0
			prev = s[i]
	print(res if prev else count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	prev = None
	f = False
	old = zero = 0
	for ele in s:
		if ele != '0' and (not f):
			f = True
			prev = ele
		if ele == '0':
			zero += 1
	if prev is None:
		print(zero)
		continue
	c = 0
	for i in range(len(s)):
		if s[i] == '0':
			c += 1
		elif s[i] == prev:
			zero -= c
			c = 0
			prev = s[i]
		else:
			if c >= 1:
				if c % 2 == 0:
					zero -= c
				else:
					zero -= c - 1
			c = 0
			prev = s[i]
	for i in range(len(s) - 1, -1, -1):
		if s[i] != '0':
			zero -= c
			break
	print(zero)


vojj = int(input())
for vishnesh in range(vojj):
	n = int(input())
	arr = input()
	k = set(arr)
	d = []
	ans = 0
	if len(k) == 1 and arr[0] == '0':
		print(n)
		continue
	else:
		for i in range(n - 2):
			p = arr[i:i + 2]
			if p == '+0' or p == '-0':
				d.append(i)
	for i in d:
		s = arr[i]
		i = i + 1
		c = 0
		while i < n - 1 and arr[i] == '0':
			c = c + 1
			i = i + 1
		if c % 2 and arr[i] != s:
			if arr[i] != '0':
				ans = ans + 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	arr = []
	l = 0
	ans = 0
	for i in s:
		if i == '+' or i == '-':
			arr.append(l)
			arr.append(i)
			l = 0
		else:
			l += 1
	if l != 0:
		arr.append(l)
	if len(arr) == 1:
		print(arr[0])
		continue
	for i in range(1, len(arr) - 1):
		if arr[i] == '+' or arr[i] == '-':
			if i + 2 < len(arr) and (arr[i] == '+' and arr[i + 2] == '-' or (arr[i] == '-' and arr[i + 2] == '+')):
				if arr[i + 1] % 2 != 0:
					if arr[i + 1] != 0:
						ans += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	str = input()
	a = []
	for i in range(n):
		if str[i] == '0':
			a.append(0)
		elif str[i] == '-':
			a.append(-1)
		else:
			a.append(1)
	nzero = 0
	sum = 0
	stage = 0
	for i in range(len(a)):
		if a[i] == 0:
			nzero += 1
		elif a[i] == -1:
			if stage == 1:
				sum += nzero % 2
			stage = -1
			nzero = 0
		else:
			if stage == -1:
				sum += nzero % 2
			stage = 1
			nzero = 0
		if i == n - 1:
			if stage == 0:
				sum += nzero
				nzero = 0
			else:
				nzero = 0
	print(sum)


for _ in range(int(input())):
	n = int(input())
	a = [x for x in input()]
	l = []
	b = a[0]
	for i in range(1, n):
		if a[i] == b[0]:
			b = b + a[i]
		else:
			l.append(b)
			b = a[i]
	l.append(b)
	if len(l) <= 1:
		print(l[0].count('0'))
	elif len(l) == 2:
		print(0)
	else:
		c = 0
		for i in range(1, len(l) - 1):
			if l[i][0] == '0':
				if l[i - 1][-1] != l[i + 1][0]:
					if len(l[i]) % 2 != 0:
						c = c + 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	pre = -1
	for i in range(len(s)):
		if s[i] != '0':
			pre = i
			break
	if pre == -1:
		print(n)
		continue
	i = pre
	ans = 0
	while i < len(s):
		if s[i] == '0':
			continue
		else:
			j = i + 1
			count = 0
			while j < n and s[j] == '0':
				j += 1
				count += 1
			if j < n and s[j] != s[i] and (count % 2 != 0):
				ans += 1
			i = j - 1
		i += 1
	print(ans)


test = int(input())
for z in range(test):
	n = int(input())
	s = input()
	cnt = 0
	t = ''
	for i in range(n):
		if s[i] == '+' or s[i] == '-':
			if t and t != s[i]:
				if (i - ind) % 2 == 0:
					cnt += 1
				t = s[i]
				ind = i
			else:
				t = s[i]
				ind = i
	if not t:
		print(n)
	else:
		print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s.count('0') == n:
		print(n)
	else:
		count = 0
		ind = 0
		flag = True
		temp = ''
		for i in range(len(s)):
			if (s[i] == '-' or s[i] == '+') and flag == True:
				temp = s[i]
				ind = i
				flag = False
			if s[i] != '0':
				if (i - ind) % 2 == 0 and s[i] != temp and (i - ind > 1):
					count += 1
				temp = s[i]
				ind = i
		print(count)


from collections import deque

def getCharge(s: list, node: int) -> int:
	chargeSum = 0
	if node > 0:
		chargeSum += 1 if s[node - 1] == '+' else -1 if s[node - 1] == '-' else 0
	if node < len(s) - 1:
		chargeSum += 1 if s[node + 1] == '+' else -1 if s[node + 1] == '-' else 0
	return chargeSum

def solve(s: list):
	queue = deque()
	for i in range(len(s)):
		if s[i] == '0':
			queue.append(i)
	while len(queue) > 0:
		size = len(queue)
		updates = []
		for i in range(size):
			node = queue.popleft()
			charge = getCharge(s, node)
			if charge > 0:
				updates.append((node, '+'))
			elif charge < 0:
				updates.append((node, '-'))
		for element in updates:
			s[element[0]] = element[1]
			if element[0] > 0 and s[element[0] - 1] == '0':
				queue.append(element[0] - 1)
			if element[0] < len(s) - 1 and s[element[0] + 1] == '0':
				queue.append(element[0] + 1)
	print(s.count('0'))
for _ in range(int(input())):
	n = input()
	s = [i for i in input()]
	solve(s)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count('0') == n:
		res = n
	else:
		s = s.replace('00', '')
		cnt = 0
		for i in range(1, len(s) - 1):
			if s[i] == '0':
				if s[i - 1] == '-' and s[i + 1] == '+' or (s[i - 1] == '+' and s[i + 1] == '-'):
					cnt += 1
		res = cnt
	print(res)


case = int(input())
for _ in range(case):
	n = int(input())
	s = input()
	zero = 0
	for i in range(n):
		if s[i] == '0':
			zero += 1
	if zero == n:
		print(n)
		continue
	negative = False
	zero = False
	positive = False
	res = 0
	znum = 0
	for i in range(n):
		if s[i] == '-':
			if zero and positive and (znum & 1 == 1):
				res += 1
			negative = True
			positive = False
			zero = False
			znum = 0
		if s[i] == '0':
			zero = True
			znum += 1
		if s[i] == '+':
			if zero and negative and (znum & 1 == 1):
				res += 1
			positive = True
			negative = False
			zero = False
			znum = 0
	print(res)


from sys import stdin, stdout
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input().split()))

def solve():
	n = r_int()
	l = input().strip()
	start = False
	xs = []
	marker = False
	for (i, x) in enumerate(l):
		if x == '0':
			if start is None:
				start = i
		else:
			marker = True
			if start is not None:
				if start != 0:
					xs.append((start, i - 1))
				start = None
	if not xs:
		if marker:
			print(0)
		else:
			print(n)
		return
	acc = 0
	for (s, e) in xs:
		if l[s - 1] != l[e + 1] and (e - s) % 2 == 0:
			acc += 1
	print(acc)

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


for i in range(int(input())):
	n = int(input())
	s = input()
	s1 = ''
	e1 = ''
	ans = 0
	for i in range(n):
		if (len(s1) == 0 or s1[0] == s[i]) and s[i] == '+':
			s1 = ['+', i]
		elif (len(s1) == 0 or s1[0] == s[i]) and s[i] == '-':
			s1 = ['-', i]
		if len(s1) > 0:
			if s1[0] == '+' and s[i] == '-':
				e1 = ['-', i]
				if abs(s1[1] - e1[1] - 1) % 2 != 0:
					ans = ans + 1
					s1 = e1
					e1 = ''
				else:
					s1 = e1
					e1 = ''
			elif s1[0] == '-' and s[i] == '+':
				e1 = ['+', i]
				if abs(s1[1] - e1[1] - 1) % 2 != 0:
					ans = ans + 1
					s1 = e1
					e1 = ''
				else:
					s1 = e1
					e1 = ''
	if '+' not in s and '-' not in s:
		print(s.count('0'))
	else:
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(nzs, nze) = (0, 0)
	for i in range(n):
		if s[i] != '0':
			nzs = i
			break
	else:
		nzs = n
	for i in range(n - 1, -1, -1):
		if s[i] != '0':
			nze = i
			break
	else:
		nze = -1
	if nzs != n and nze != -1:
		charge = s[nzs]
		res = 0
		c = 0
		for i in range(nzs + 1, nze + 1):
			if s[i] == '0':
				c += 1
			else:
				if s[i] != charge:
					charge = s[i]
					if c % 2 == 1:
						res += 1
				c = 0
		print(res)
	else:
		print(n)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	if l.count('0') == n:
		print(n)
	else:
		l = l.replace('00', '')
		c = 0
		for i in range(1, len(l) - 1):
			if l[i] == '0':
				if l[i - 1] == '+' and l[i + 1] == '-' or (l[i - 1] == '-' and l[i + 1] == '+'):
					c += 1
		print(c)


for t in range(int(input())):
	n = int(input())
	s = input()
	(ans, length, charge) = (0, 0, 'x')
	for j in range(n):
		if s[j] == '0':
			length += 1
		else:
			if s[j] != charge and charge != 'x' and (length % 2 == 1):
				ans += 1
			charge = s[j]
			length = 0
	if charge == 'x':
		ans = n
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	p = []
	for i in range(n):
		if s[i] != '0':
			p.append((i, s[i]))
	ctr = 0
	z = s.count('0')
	for i in range(len(p) - 1):
		if p[i][1] != p[i + 1][1] and (p[i + 1][0] - p[i][0]) % 2 == 0:
			ctr += 1
	if z != n:
		print(ctr)
	else:
		print(z)


for _ in range(int(input())):
	n = int(input())
	s = input()
	prev = None
	ans = c = 0
	i = 0
	if s.count('0') == n:
		print(n)
	else:
		while i < n:
			zCount = 0
			while i < n and s[i] == '0':
				i += 1
				zCount += 1
			if i == n:
				continue
			if zCount > 0 and prev != None and (prev != s[i]):
				ans += zCount & 1
			prev = s[i]
			i += 1
		print(ans)


def oppo(x):
	return '+' if x == '-' else '-'
for _ in range(int(input())):
	n = int(input())
	s = input()
	(st, cc) = ([], 0)
	for c in s:
		if c == '0' and len(st) != 0 and (st[-1] == '0'):
			st.pop()
			continue
		st.append(c)
	for i in range(1, len(st) - 1):
		if st[i] == '0' and st[i + 1] == oppo(st[i - 1]):
			cc += 1
	if len(st) == 0 or (len(st) == 1 and st[0] == '0'):
		print(n)
	else:
		print(cc)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	while s.count('000'):
		s = s.replace('000', '0')
	p = '+' in s
	q = '-' in s
	if p | q:
		print(s.count('-0+') + s.count('+0-'))
	else:
		print(n)


for i in range(int(input())):
	n = int(input())
	s = input()
	if set(s) == {'0'}:
		print(n)
	else:
		while '000' in s:
			s = s.replace('000', '0')
		print(s.count('+0-') + s.count('-0+'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	cur_charge = 0
	cur_idx = 0
	pre_charge = 0
	neutrals = 0
	for i in range(n):
		if s[i] != '0':
			if s[i] == '+':
				cur_charge = 1
			else:
				cur_charge = -1
			cur_idx = i
			if pre_charge + cur_charge == 0:
				if (cur_idx - pre_idx) % 2 == 0:
					neutrals += 1
			pre_charge = cur_charge
			pre_idx = cur_idx
	if pre_charge == 0 and cur_charge == 0:
		print(n)
	else:
		print(neutrals)


for i in range(int(input())):
	n = int(input())
	s = input()
	(ans, len, cur) = (0, 0, 'x')
	for j in range(n):
		if s[j] == '0':
			len += 1
		else:
			if s[j] != cur and cur != 'x' and (len % 2 == 1):
				ans += 1
			cur = s[j]
			len = 0
	if cur == 'x':
		ans = n
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 0
	ct = 0
	sgn = 0
	for i in s:
		if i == '0':
			ct += 1
		elif sgn == 0:
			sgn = i
			ct = 0
		elif ct % 2 == 1:
			if i != sgn:
				ans += 1
				sgn = i
				ct = 0
			else:
				ct = 0
				sgn = i
		else:
			sgn = i
			ct = 0
	if ct == n:
		ans = n
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	assert len(s) == n
	if s.count('0') == n:
		print(n)
		continue
	last = -1
	count = 0
	for i in range(n):
		if s[i] != '0':
			if last >= 0 and i % 2 == last % 2:
				left = s[last]
				right = s[i]
				if left == '-' and right == '+' or (left == '+' and right == '-'):
					count += 1
			last = i
	print(count)


import re
for i in range(int(input())):
	l = int(input())
	N = input()
	if '+' not in N and '-' not in N:
		print(l)
	else:
		r1 = re.findall('\\+(00)*0\\-', N)
		r2 = re.findall('\\-(00)*0\\+', N)
		rt = len(r1) + len(r2)
		print(rt)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	d = Counter(s)
	if d['0'] == n:
		print(n)
	else:
		s = s.replace('00', '')
		ans = 0
		for i in range(1, len(s) - 1):
			if s[i] == '0':
				if s[i - 1] == '-' and s[i + 1] == '+' or (s[i - 1] == '+' and s[i + 1] == '-'):
					ans += 1
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = list(s)
	charge = False
	count = 0
	dict = {}
	for p in range(n):
		if s[p] == '+':
			dict[p] = '+'
		elif s[p] == '-':
			dict[p] = '-'
	if dict == {}:
		print(n)
	elif '-' not in list(dict.values()):
		print(0)
	elif '+' not in list(dict.values()):
		print(0)
	else:
		listkey = list(dict.keys())
		count = 0
		for x in range(len(listkey) - 1):
			if dict[listkey[x]] == '+' and dict[listkey[x + 1]] == '-':
				if (listkey[x + 1] - listkey[x]) % 2 == 0:
					count += 1
			elif dict[listkey[x]] == '-' and dict[listkey[x + 1]] == '+':
				if (listkey[x + 1] - listkey[x]) % 2 == 0:
					count += 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	l = input()
	if l.count('0') == n:
		print(n)
	else:
		l = l.replace('00', '')
		c = 0
		for i in range(1, len(l) - 1):
			if l[i] == '0':
				if l[i - 1] == '+' and l[i + 1] == '-' or (l[i - 1] == '-' and l[i + 1] == '+'):
					c += 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	l = input()
	if n * '0' == l:
		print(n)
		continue
	cur = None
	prev = None
	ans = 0
	cur_o = 0
	for (pos, i) in enumerate(l):
		if i != '0':
			cur = i
			if prev != None and cur != prev:
				ans += 1 if cur_o & 1 else 0
			prev = cur
			cur_o = 0
		else:
			cur_o += 1
	print(ans)


for i in range(int(input())):
	m = int(input())
	s = input()
	if s.count('0') == m:
		print(m)
	else:
		s = s.replace('00', '')
		count = 0
		for j in range(1, len(s) - 1):
			if s[j] == '0':
				if s[j - 1] == '+' and s[j + 1] == '-' or (s[j - 1] == '-' and s[j + 1] == '+'):
					count += 1
		print(count)


t = int(input())
list_input = []
for i in range(t):
	n = int(input())
	s = input()
	list_input.append([n, s])
for i in range(t):
	s = list_input[i][1]
	count = 0
	count1 = 0
	flag = 't'
	(s_id, e_id) = (-1, -1)
	for j in range(len(s)):
		if s[j] != '0':
			s_id = j
			flag = s[j]
			break
	if s_id == -1:
		print(len(s))
		continue
	for j in reversed(range(len(s))):
		if s[j] != '0':
			e_id = j
			break
	for j in range(s_id + 1, e_id + 1):
		if s[j] == '0':
			count1 = count1 + 1
		elif s[j] == '+':
			if flag == '+':
				count1 = 0
				flag = '+'
			if flag == '-':
				if count1 != 0 and count1 % 2 != 0:
					count = count + 1
				count1 = 0
				flag = '+'
		else:
			if flag == '-':
				count1 = 0
				flag = '-'
			if flag == '+':
				if count1 != 0 and count1 % 2 != 0:
					count = count + 1
				count1 = 0
				flag = '-'
	print(count)


numTest = int(input())
for _ in range(numTest):
	n = int(input())
	s = input()
	ans = 0
	cnt0 = 0
	chrg = '0'
	for i in s:
		if i == '0':
			cnt0 += 1
		else:
			if chrg == '0':
				pass
			elif chrg != i and cnt0 % 2 == 1:
				ans += 1
			chrg = i
			cnt0 = 0
	if chrg == '0':
		ans = n
	print(ans)


for t in range(int(input())):
	n = int(input())
	s = input()
	c1 = c = S = E = 0
	check = True
	for i in range(0, n):
		if s[i] == '0':
			c1 += 1
		if s[i] == '0' and check:
			S = i
			E = i
			check = False
		elif s[i] == '0':
			E = i
		else:
			check = True
			if S != 0 and E != n - 1:
				if s[S - 1] == '+' and s[E + 1] == '-' or (s[S - 1] == '-' and s[E + 1] == '+'):
					if (E - S + 1) % 2 != 0:
						c += 1
			S = E = 0
	if c1 == n:
		c = c1
	print(c)


import re
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count('0') == n:
		print(n)
	else:
		s = re.sub('(00)+', '', s)
		print(s.count('-0+') + s.count('+0-'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	val = [0] * n
	charge = 0
	for i in range(n):
		if s[i] == '+':
			charge = 1
		elif s[i] == '-':
			charge = -1
		else:
			if charge > 0:
				charge += 1
			if charge < 0:
				charge -= 1
		val[i] = charge
	charge = 0
	for i in reversed(range(n)):
		if s[i] == '+':
			charge = 1
		elif s[i] == '-':
			charge = -1
		else:
			if charge > 0:
				charge += 1
			if charge < 0:
				charge -= 1
		val[i] += charge
	print(val.count(0))


for te in range(int(input())):
	n = int(input())
	s = input()
	while '000' in s:
		s = s.replace('000', '0')
	if set(s) == {'0'}:
		print(n)
	else:
		k = s.count('-0+')
		m = s.count('+0-')
		print(k + m)


for _ in range(int(input())):
	_ = int(input())
	s = list(input())
	n = len(s)
	cnt_0 = s.count('0')
	if cnt_0 == n or cnt_0 == 0:
		print(cnt_0)
		continue
	(l, r) = (None, None)
	tmp_cnt_0 = 0
	for c in s:
		if c == '0':
			tmp_cnt_0 += 1
			continue
		if l is None:
			cnt_0 -= tmp_cnt_0
			tmp_cnt_0 = 0
		elif tmp_cnt_0 > 0:
			if l == c or tmp_cnt_0 % 2 == 0:
				cnt_0 -= tmp_cnt_0
			else:
				cnt_0 -= tmp_cnt_0 - 1
			tmp_cnt_0 = 0
		l = c
	if tmp_cnt_0 > 0:
		cnt_0 -= tmp_cnt_0
	print(cnt_0)


for _ in range(int(input())):
	n = int(input())
	h = list(input())
	counter = 0
	store = 0
	sign = '0'
	for i in range(n):
		if h[i] == '+':
			if sign == '-':
				sign = '+'
				if counter != 0:
					if counter % 2 != 0:
						store += 1
					counter = 0
			if sign == '0':
				sign = '+'
				counter = 0
			if sign == '+':
				counter = 0
		if h[i] == '-':
			if sign == '+':
				sign = '-'
				if counter != 0:
					if counter % 2 != 0:
						store += 1
					counter = 0
			if sign == '0':
				sign = '-'
				counter = 0
			if sign == '-':
				counter = 0
		if h[i] == '0':
			counter += 1
	if sign != '0':
		print(store)
	else:
		print(counter)


from collections import Counter
a = int(input())
for _ in range(a):
	y = int(input())
	b = input()
	g = False
	e = False
	t = False
	p = False
	co = 0
	m = 0
	l = Counter(b)
	if l['0'] == len(b):
		print(len(b))
	else:
		for i in b:
			if i == '-' and g == True and (p == True):
				p = False
				g = False
				e = True
				if m % 2 == 1:
					co += 1
				m = 0
			elif i == '+' and e == True and (p == True):
				p = False
				e = False
				g = True
				if m % 2 == 1:
					co += 1
				m = 0
			elif i == '+':
				g = True
				e = False
				p = False
				m = 0
			elif i == '0':
				p = True
				m += 1
			elif i == '-':
				e = True
				g = False
				p = False
				m = 0
		print(co)


n = int(input())
while n:
	n -= 1
	s = int(input())
	i = input()
	c = 0
	for j in i:
		if j == '0':
			c += 1
	while 1:
		if '000' in i:
			i = i.replace('000', '0')
		else:
			break
	if c == s:
		print(s)
	else:
		an = i.count('-0+') + i.count('+0-')
		print(an)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	z = 0
	for i in range(n):
		if s[i] != '0':
			l.append([i, s[i]])
		else:
			z += 1
	c = 0
	for j in range(len(l) - 1):
		if l[j][1] != l[j + 1][1] and (l[j + 1][0] - l[j][0]) % 2 == 0:
			c += 1
	if z != n:
		print(c)
	else:
		print(z)


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	while '000' in s:
		s = s.replace('000', '0')
	if set(s) == set('0'):
		print(n)
	else:
		print(s.count('-0+') + s.count('+0-'))


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	curr = ''
	for i in range(n):
		if s[i] == '+' or s[i] == '-':
			curr = s[i]
			break
	if curr == '':
		print(n)
	else:
		(v, ans) = (0, 0)
		for j in range(i + 1, n):
			if s[j] == '0':
				v += 1
			else:
				if curr != s[j] and v & 1:
					ans += 1
				curr = s[j]
				v = 0
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	objects = input()
	(l_c, n_0) = ([], objects.count('0'))
	for j in range(n):
		if objects[j] == '+':
			l_c.append([j + 1, 1])
		elif objects[j] == '-':
			l_c.append([j + 1, -1])
	if len(l_c) == 0:
		print(n_0)
	else:
		if len(l_c) != 1:
			for x in range(len(l_c) - 1):
				if l_c[x][1] != l_c[x + 1][1] and l_c[x + 1][0] - l_c[x][0] != 1 and ((l_c[x + 1][0] - l_c[x][0] - 1) % 2 != 0):
					n_0 -= l_c[x + 1][0] - l_c[x][0] - 2
				elif l_c[x][1] != l_c[x + 1][1] and l_c[x + 1][0] - l_c[x][0] != 1 and ((l_c[x + 1][0] - l_c[x][0] - 1) % 2 == 0):
					n_0 -= l_c[x + 1][0] - l_c[x][0] - 1
				elif l_c[x][1] == l_c[x + 1][1] and l_c[x + 1][0] - l_c[x][0] != 1:
					n_0 -= l_c[x + 1][0] - l_c[x][0] - 1
		n_0 -= l_c[0][0] - 1 + (len(objects) - l_c[-1][0])
		print(n_0)


t = int(input())
while t:
	n = int(input())
	li = input()
	prev = 0
	lastzero = -1
	prev = '0'
	ans = 0
	zeroes = 0
	zerocount = 0
	for i in range(n):
		if li[i] == '+' or li[i] == '-':
			if prev == '0':
				prev = li[i]
				previndex = i
				zeroes = 0
			elif prev == li[i]:
				previndex = i
				zeroes = 0
			else:
				if zeroes % 2 == 1:
					ans += 1
				prev = li[i]
				previndex = i
				zeroes = 0
		else:
			zerocount += 1
			zeroes += 1
			lastzero = i
	if zerocount == n:
		print(n)
	else:
		print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = [0, 0, 0]
	c = 0
	if s.count('0') == n:
		print(n)
	else:
		for i in s:
			if i == '0' and (l[0] == 1 or l[2] == 1):
				l[1] += 1
			elif i == '+' and (l[0] == 1 or (l[2] == 1 and l[1] == 0)):
				l = [1, 0, 0]
			elif i == '-' and (l[2] == 1 or (l[0] == 1 and l[1] == 0)):
				l = [0, 0, 1]
			elif i == '+' and l[0] == 0:
				l[0] = 1
			elif i == '-' and l[2] == 0:
				l[2] = 1
			if l[0] > 0 and l[1] > 0 and (l[2] > 0):
				if l[1] % 2 != 0:
					c += 1
				l = [0, 0, 0]
				if i == '+':
					l[0] = 1
				elif i == '-':
					l[2] = 1
		print(c)


n = int(input())
while n:
	n -= 1
	s = int(input())
	i = input()
	while 1:
		if '000' in i:
			i = i.replace('000', '0')
		else:
			break
	if set(i) == set('0'):
		print(s)
	else:
		an = i.count('-0+') + i.count('+0-')
		print(an)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	n = 0
	c = 0
	prev = '0'
	for s in S:
		if s == '0':
			c += 1
		else:
			if prev == '0':
				c = 0
			elif prev != s:
				if c % 2 == 1:
					n += 1
			c = 0
			prev = s
	if prev == '0':
		n = c
	print(n)


for i in range(int(input())):
	a = int(input())
	b = input()
	while '000' in b:
		b = b.replace('000', '0')
	if set(b) == {'0'}:
		print(a)
	else:
		x = b.count('-0+')
		y = b.count('+0-')
		print(x + y)


for _ in range(int(input())):
	n = int(input())
	st = [i for i in input()]
	(c1, c, s, e) = (0, 0, 0, 0)
	f = 1
	for i in range(n):
		if st[i] == '0':
			c1 += 1
		if st[i] == '0' and f:
			(s, e) = (i, i)
			f = 0
		elif st[i] == '0':
			e = i
		else:
			f = 1
			if s != 0 and e != n - 1:
				if st[s - 1] == '+' and st[e + 1] == '-' or (st[s - 1] == '-' and st[e + 1] == '+'):
					if (e - s + 1) % 2 != 0:
						c += 1
				s = e = 0
	if c1 == n:
		c = c1
	print(c)


N = int(input())
for _ in range(N):
	A = int(input())
	s = input()
	while '000' in s:
		s = s.replace('000', '0')
	if set(s) == set('0'):
		print(A)
	else:
		print(s.count('-0+') + s.count('+0-'))


k = int(input())
for i in range(k):
	n = int(input())
	s = input()
	p = 0
	n = 0
	c = 0
	neu = 0
	f = 0
	for v in s:
		if v == '+':
			if n == 1 and c > 0 and (c % 2 == 1):
				neu += 1
			n = 0
			p = 1
			c = 0
			f = 1
		if v == '-':
			if p == 1 and c > 0 and (c % 2 == 1):
				neu += 1
			n = 1
			p = 0
			c = 0
			f = 1
		if v == '0':
			c += 1
	if f == 0:
		neu += c
	print(neu)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c1 = 0
	c = 0
	sc = 0
	ne = 0
	temp = True
	for i in range(n):
		if s[i] == '0':
			c1 += 1
		if s[i] == '0' and temp:
			sc = i
			ne = i
			temp = False
		elif s[i] == '0':
			ne = i
		else:
			temp = True
			if sc != 0 and ne != n - 1:
				if s[sc - 1] == '+' and s[ne + 1] == '-' or (s[sc - 1] == '-' and s[ne + 1] == '+'):
					if (ne - sc + 1) % 2 != 0:
						c += 1
			sc = ne = 0
	if c1 == n:
		c = c1
	print(c)


t = int(input())
for j in range(t):
	n = int(input())
	str = input()
	(a1, a2) = (0, 0)
	(Str, Eve) = (0, 0)
	checking = True
	for i in range(n):
		if str[i] == '0':
			a1 += 1
		if str[i] == '0' and checking:
			Str = i
			Eve = i
			checking = False
		elif str[i] == '0':
			Eve = i
		else:
			checking = True
			if Str != 0 and Eve != n - 1:
				if str[Str - 1] == '+' and str[Eve + 1] == '-' or (str[Str - 1] == '-' and str[Eve + 1] == '+'):
					if (Eve - Str + 1) % 2 != 0:
						a2 += 1
			Str = Eve = 0
	if a1 == n:
		a2 = a1
	print(a2)


for i in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	b = 0
	v = []
	for j in range(n):
		if s[j] != '0':
			v.append(j)
	if len(v) == 1:
		print(0)
	elif len(v) == 0:
		print(n)
	else:
		for k in range(len(v) - 1):
			if s[v[k]] != s[v[k + 1]]:
				x = v[k + 1] - v[k] - 1
				if x % 2 != 0:
					count += 1
		print(count)