You are given a binary string S of length N. 

You can perform the following operation on S:
Select an index i \ (1 ≤ i < |S|) such that S_{i}=S_{i+1}.
Set S_{i} to 0 and remove S_{i+1} from the string.

Note that after each operation, the length of S decreases by 1.

Is it possible to reduce S to a single character by performing the mentioned operation exactly N-1 times?

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

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, the length of S.
- The second line contains a binary string S of length N.

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

For each test case, print the answer on a new line: YES if it is possible to perform the operation N-1 times, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, YES, yes, yEs and yES will all be treated as identical.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
- The sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
11
2
10
4
1100
3
101

----- Sample Output 1 ------ 
YES
NO
YES
NO

----- explanation 1 ------ 
Test case $1$: Perform the operation choosing $i = 1$. This sets $S_{1} = 0$ and deletes $S_{2}$ from the string, after which $S$ is now a single character.

Test case $2$: It is not possible to perform any operation.

Test case $3$: One sequence of operations is as follows:
- Perform the operation on $i = 3$. Now, $S = 110$.
- Perform the operation on $i = 1$. Now, $S = 00$.
- Perform the operation on $i = 1$. Now, $S = 0$ and we are done.

Test case $4$: It is not possible to perform any operation.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	while '11' in s or '00' in s:
		s = s.replace('11', '0')
		s = s.replace('00', '0')
	if len(s) == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	flag = False
	if n == 1:
		print('YES')
	else:
		count = 0
		for i in s:
			if i == '1':
				count += 1
			else:
				if count % 2 == 1:
					flag = True
					print('NO')
					break
				count = 0
		if flag != True:
			if count % 2 == 0:
				print('YES')
			else:
				print('NO')


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	flag = 0
	if n == 1:
		print('YES')
		continue
	for (key, val) in groupby(s):
		if key == '1' and len(list(val)) % 2 == 1:
			print('NO')
			flag = 1
			break
	if not flag:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	k = 0
	x = 0
	while k < n and x < len(s) - 1:
		if s[x] == s[x + 1]:
			s = s[0:x] + '0' + s[x + 2:len(s)]
			k = k + 1
			x = 0
			continue
		x = x + 1
	if len(s) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	ones = s.split('0')
	red = all([len(o) % 2 == 0 for o in ones])
	if n == 1:
		red = True
	if red == True:
		print('YES')
	if red == False:
		print('NO')


for forbid in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in s:
		if i == '1':
			count += 1
		if i == '0' and count % 2 != 0:
			break
	if count % 2 != 0 and n > 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	on = 0
	ans = 'YES'
	for c in input():
		if c == '1':
			on += 1
		else:
			if on % 2 == 1:
				ans = 'NO'
				break
			on = 0
	if on % 2 == 1 and n > 1:
		ans = 'NO'
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	while True:
		if len(s) == 1:
			print('YES')
			break
		for i in range(0, len(s)):
			if i == len(s) - 1:
				continue
			if s[i] == s[i + 1]:
				s = s.replace(s[i:i + 2], '0', 1)
				break
		else:
			print('NO')
			break


from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	x = 0
	if n == 1:
		print('YES')
	else:
		f = 0
		while x < n - 1:
			if s[x] == '1' and s[x + 1] != '1':
				f = 1
				break
			elif s[x] == '1':
				x += 1
			x += 1
		if s[n - 1] == '1' and x != n:
			f = 1
		if f:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
		continue
	for ones in s.split('0'):
		if len(ones) % 2 == 1:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	else:
		s = s.replace('11', '0')
		k = s.count('1')
		if k > 0:
			print('NO')
		else:
			print('YES')


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)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	if N == 1:
		ans.append('YES')
	else:
		ans.append('NO' if '1' in S.replace('11', '0') else 'YES')
outplt(ans)


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)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	if N == 1:
		ans.append('YES')
		continue
	ones = False
	for s in S:
		if s == '1':
			ones = not ones
		elif ones:
			break
	ans.append('NO' if ones else 'YES')
outplt(ans)


for _ in range(int(input())):
	a = int(input())
	b = input()
	s = 0
	i = 0
	if a == 1:
		print('YES')
	else:
		while i < a:
			if b[i] == '1':
				if i < a - 1 and b[i + 1] == '1':
					i = i + 1
				else:
					s = 1
					print('NO')
					break
			i = i + 1
		if s == 0:
			print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = True
	while flag and len(s) > 1:
		flag = False
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				if i + 1 != len(s) - 1:
					s = s[:i] + '0' + s[i + 2:]
				else:
					s = s[:i] + '0'
				flag = True
				break
	if len(s) == 1:
		print('YES')
	else:
		print('NO')


import itertools
for _ in range(int(input())):
	if int(input()) == 1:
		print('YES')
		_ = input()
	else:
		for (k, v) in itertools.groupby(input()):
			if k == '1' and len(list(v)) & 1:
				print('NO')
				break
		else:
			print('YES')


def ans(l):
	if len(l) == 1:
		return 'YES'
	for i in l:
		if i:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	for i in s:
		l.append(int(i))
	i = 0
	while i < n - 1:
		if not l[i] ^ l[i + 1]:
			l[i] = 0
			l[i + 1] = 0
			i += 1
		i += 1
	print(ans(l))


t = int(input())
for i in range(t):
	n = int(input())
	b = list(input())
	i = 0
	while i < n - 1:
		if b[i] == b[i + 1]:
			b[i] = '0'
			b.pop(i + 1)
			i = 0
			n -= 1
		else:
			i += 1
	if len(b) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	x = input()
	i = 0
	f = 0
	c = 0
	if n == 1:
		print('YES')
	elif n == 2:
		if x == '01' or x == '10':
			print('NO')
		else:
			print('YES')
	else:
		if x[len(x) - 3:] == '010' or x[len(x) - 3:] == '101':
			f = 1
		while i < n - 1:
			if x[i] == '1':
				if x[i + 1] == '0':
					f = 1
					break
				else:
					i += 2
					c += 1
			else:
				i += 1
		if f == 1:
			print('NO')
		elif x.count('0') + 2 * c - 1 == n - 1:
			print('YES')
		else:
			print('NO')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	if n == 1:
		print('YES')
	else:
		cnt = 0
		while True:
			c = 0
			for i in range(len(s) - 1):
				if s[i] == s[i + 1]:
					cnt += 1
					s = s[:i] + '0' + s[i + 2:]
					c = 1
					break
			if c == 0:
				break
		if len(s) == 1 and cnt <= n - 1:
			print('YES')
		else:
			print('NO')


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	s = str(input())
	fl = 0
	ec = 0
	if n == 1:
		print('YES')
	else:
		for i in range(n):
			if s[i] == '1' and fl == 0:
				fl = 1
			elif s[i] == '0' and fl == 1:
				print('NO')
				ec = 1
				break
			elif s[i] == '1' and fl == 1:
				fl = 0
		if fl == 1 and ec == 0:
			print('NO')
		if fl == 0:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
		continue
	x = s.split('0')
	f = 0
	for i in x:
		if i.count('1') % 2 != 0:
			f = 1
			break
	if f == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	if len(s) == 1:
		print('YES')
		continue
	i = 0
	flag = 1
	while i < n:
		c = 0
		j = i
		while i < n and s[i] == '1':
			c += 1
			i += 1
		if c % 2 != 0:
			flag = 0
			break
		if i == j:
			i += 1
	if flag == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = True
	count = 0
	if n > 1:
		for i in range(n):
			if s[i] == '1':
				count += 1
			elif count % 2 == 1:
				ans = False
				break
			else:
				count = 0
		if count % 2 == 1:
			ans = False
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = b.replace('11', '0')
	if a == 1:
		print('YES')
	elif '1' in c:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	b = string.replace('11', '0')
	if n == 1:
		print('YES')
	elif '1' in b:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	n = int(input())
	s = input()
	s = s + '0'
	one_length = 0
	flag = 1
	if len(s) != 2:
		for i in range(len(s)):
			if s[i] == '1':
				one_length += 1
			else:
				if one_length % 2 != 0:
					flag = 0
					break
				one_length = 0
		if flag:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
	t -= 1


tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	ans = 'YES'
	j = 0
	while j < length - 1:
		if string[j] != string[j + 1]:
			if string[j] == '0':
				j += 1
			else:
				ans = 'NO'
				break
		else:
			j += 2
	if j == length - 1 and string[j] != '0' and (length != 1):
		ans = 'NO'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	i = 0
	ans = 'YES'
	while n != 1 and i < n:
		j = i
		while i < n and s[i] == '1':
			i += 1
		if (i - j) % 2 != 0:
			ans = 'NO'
			break
		if j == i:
			i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	flag = 0
	for i in range(n):
		if s[i] == '1':
			count += 1
		elif s[i] == '0' and count % 2 == 0:
			count = 0
		else:
			flag = 1
			break
	if n != 1 and (flag or count % 2 == 1):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	o = s.count('1')
	d = s.count('11')
	if n == 1 or 2 * d == o:
		print('YES')
	else:
		print('NO')


from itertools import groupby as gb
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	else:
		x = [(i, len(list(j))) for (i, j) in gb(s)]
		flag = 0
		for (i, j) in x:
			if i == '1' and j % 2 == 1:
				print('NO')
				flag = 1
				break
		if flag == 0:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	double = s.count('11')
	if ones % 2 == 0 and double == ones // 2 or n == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	ones = S.count('1')
	double = S.count('11')
	if ones % 2 == 0 and double == ones // 2 or N == 1:
		print('YES')
	else:
		print('NO')


from collections import Counter, defaultdict
import sys

def sol(n, s):
	if n == 1:
		return 1
	if n == 2:
		if s[0] == s[1]:
			return 1
		return 0
	s_new = ''
	curr = s[0]
	s_new += s[0]
	for i in range(1, n):
		if s[i] == curr and curr == '0':
			continue
		else:
			s_new += s[i]
			curr = s[i]
	locs = []
	for i in range(len(s_new)):
		if s_new[i] == '0':
			locs.append(i)
	if len(locs) == 0:
		if len(s_new) % 2 == 0:
			return 1
		return 0
	if locs[0] % 2 != 0:
		return 0
	if (len(s_new) - locs[-1] - 1) % 2 != 0:
		return 0
	for i in range(1, len(locs)):
		if (locs[i] - locs[i - 1] - 1) % 2 != 0:
			return 0
	return 1
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	s = insr()
	if sol(n, s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	oc = s.count('1')
	doc = s.count('11')
	if n == 1 or oc == 2 * doc:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = input()
	q = a.count('11')
	p = a.count('1')
	if p == 2 * q or n == 1:
		print('YES')
	else:
		print('NO')


for test in range(int(input())):
	n = int(input())
	arr = input()
	if n == 1:
		print('YES')
	else:
		cnt_ones = 0
		for i in arr:
			if i == '1':
				cnt_ones += 1
		if cnt_ones % 2 == 1:
			print('NO')
		else:
			cnt_11_subs = arr.count('11')
			if cnt_11_subs * 2 == cnt_ones:
				print('YES')
			else:
				print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	pairones = s.count('11')
	singleones = s.count('1')
	if pairones * 2 == singleones or n == 1:
		print('YES')
	else:
		print('NO')


def make_one(s_len, s):
	ans = 'NO'
	cnt = s_len
	for i in range(s_len):
		if cnt == 1:
			ans = 'YES'
			break
		elif any((substring in s for substring in list_check)) and cnt > 1:
			s = s.replace('00', '0')
			s = s.replace('11', '0')
			cnt = len(s)
		else:
			break
	print(ans)
for _ in range(int(input())):
	s_len = int(input())
	s = str(input())
	list_check = ['00', '11']
	make_one(s_len, s)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	else:
		i = 0
		done = False
		while i < n:
			j = i
			while j < n and s[j] == '1':
				j += 1
			if j - i & 1:
				done = True
				break
			i = j + 1
		if done:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	st = input()
	ans = 'YES'
	if n == 1:
		print(ans)
		continue
	ct = 0
	for i in st:
		if i == '1':
			ct = ct + 1
		else:
			if ct % 2 == 1:
				ans = 'NO'
				break
			ct = 0
	if ct % 2 == 1:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	length = int(input())
	str = input()
	ans = 'YES'
	onescount = 0
	for char in str:
		if char == '1':
			onescount += 1
		else:
			if onescount & 1:
				ans = 'NO'
			ones = 0
	if onescount & 1 and length > 1:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	N = int(input())
	S = input()
	cur = S
	i = 0
	while i < len(cur) - 1 and ('00' in cur or '11' in cur):
		cur = cur.replace('00', '0')
		cur = cur.replace('11', '0')
	if len(cur) == 1:
		print('YES')
	else:
		print('NO')


def solve2():
	n = int(input())
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if n == 1:
		print('YES')
		return
	elif one % 2 != 0:
		print('NO')
		return
	temp = 0
	for i in range(n - 1):
		if s[i] == '1':
			temp += 1
		else:
			if temp % 2 != 0:
				print('NO')
				return
			temp = 0
	print('YES')

def solve1():
	for _ in range(int(input())):
		solve2()
solve1()


for i in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeros = s.count('0')
	done = True
	if len(s) == 1:
		print('YES')
	elif ones % 2 != 0:
		print('NO')
	else:
		count = 0
		for i in s:
			if i == '1':
				count += 1
			else:
				if count % 2 != 0:
					done = False
					break
				count = 0
		if count % 2 != 0:
			done = False
		if done:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	a = int(input())
	b = input()
	k = b.count('11')
	q = b.count('1')
	if q == 2 * k or a == 1:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	n = int(input())
	p = input()
	a = p.count('11')
	b = p.count('1')
	if b == 2 * a or n == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	s = input()
	a = s.count('11')
	b = s.count('1')
	if b == a * 2 or len(s) == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	a = int(input())
	b = input()
	if a == 2 and len(set(b)) == 1 or len(b) == 1:
		print('YES')
	elif b == 2:
		print('NO')
	else:
		b = b.replace('11', '0')
		if b.count('1'):
			print('NO')
		else:
			print('YES')