Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string $s$ as input. However, they soon found out that if some substring $t$ of $s$ is a palindrome of length greater than 1, the algorithm will work incorrectly. Can the students somehow reorder the characters of $s$ so that the algorithm will work correctly on the string?

A binary string is a string where each character is either 0 or 1.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A palindrome is a string that reads the same backwards as forwards.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the string $s$.

The second line of each test case contains the string $s$ of length $n$ consisting only of the characters 0 and 1.


-----Output-----

For each test case, print YES (case-insensitive) if it is possible to reorder the characters of $s$ so that there are no substrings that are a palindrome of length greater than 1, or NO (case-insensitive) otherwise.


-----Examples-----

Input
4
1
1
2
10
2
01
4
1010
Output
YES
YES
YES
NO


-----Note-----

In the first three test cases, the given strings do not contain palindromes of length greater than 1, so the answers are YES.

In the last test case, it is impossible to reorder the characters so that the string does not contain palindromes of length greater than 1, so the answer is NO.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	n = int(input())
	k = input()
	if len(k) <= 1:
		print('YES')
	elif len(k) == 2:
		if k[0] != k[1]:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip()
	if s == '01' or s == '0' or s == '1' or (s == '10'):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n >= 3:
		print('NO')
	elif n == 2:
		if s[0] == s[1]:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s == '00' or s == '11':
		print('NO')
	elif len(s) > 2:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	input()
	if input() in ['0', '1', '01', '10']:
		print('YES')
	else:
		print('NO')


t = int(input())
out = []
yes = ['0', '1', '01', '10']
for x in range(t):
	n = int(input())
	s = input()
	if s in yes:
		out.append('YES')
	else:
		out.append('NO')
for ans in out:
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s.count('0') > 1 or s.count('1') > 1:
		print('NO')
	else:
		print('YES')


def check_pal(n: int, s: str) -> (str, str):
	if n == 1:
		return 'YES'
	elif n > 2:
		return 'NO'
	elif n == 2:
		if s == '10' or s == '01':
			return 'YES'
		elif s == '11' or s == '00':
			return 'NO'
t = input()
for _ in range(int(t)):
	val = []
	for _ in range(2):
		val.append(input())
	print(check_pal(int(val[0]), val[1]))


def check_palindrome(N):
	binary = bin(N)
	length = len(binary)
	binary = binary[2:length]
	length = len(binary)
	if binary == '1':
		return 0
	for i in range(length):
		if binary[i] != binary[length - i - 1]:
			return 0
	return 1
T = int(input())
for count in range(T):
	L = int(input())
	string = input()
	if L == 1:
		print('YES')
		continue
	str1 = ''
	str0 = ''
	for i in string:
		if i == '1':
			str1 += i
		else:
			str0 += i
	maxval = int(str1 + str0, base=2)
	minval = int(str0 + str1, base=2)
	for i in range(minval, maxval + 1):
		res = check_palindrome(i)
		if res == 1:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input())
	jed = a.count('1')
	zer = a.count('0')
	if jed > 1 or zer > 1:
		print('NO')
	else:
		print('YES')


n = int(input())
for __ in range(n):
	size = int(input())
	s = input()
	cnt = [0, 0]
	for i in range(0, size):
		if s[i] == '1':
			cnt[1] += 1
		else:
			cnt[0] += 1
	if cnt[0] > 1 or cnt[1] > 1:
		print('NO')
	else:
		print('YES')


def check(n, s):
	if n >= 3:
		return 'NO'
	elif n == 2:
		if s.count('0') == 1:
			return 'YES'
		else:
			return 'NO'
	else:
		return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(check(n, s))


a = int(input())
for i in range(1, a + 1):
	ai = int(input())
	si = input()
	if len(si) == 1:
		print('YES')
	elif si == '10' or si == '01':
		print('YES')
	else:
		print('NO')


tot_cases = input()
tot_cases = int(tot_cases)

def isPali(a: str) -> bool:
	if a[::-1] == a:
		return True

def hasNoPali(sl: int, a: str) -> bool:
	for i in range(sl - 1):
		for j in range(i + 2, sl + 1):
			if isPali(a[i:j]):
				return False
	return True
for i in range(tot_cases):
	sl = input()
	s = input()
	if hasNoPali(int(sl), s):
		print('YES')
	else:
		print('NO')


t = int(input())
output = []
if t >= 1 and t <= 100:
	for i in range(t):
		n = int(input())
		if n >= 1 and n <= 100:
			s = input()
			if n == 1 or (n == 2 and s != '00' and (s != '11')):
				output.append('YES')
			else:
				output.append('NO')
	for o in output:
		print(o)


for s in [*open(0)][2::2]:
	print('YNEOS'[len(s) > len({*s})::2])


t = int(input())
while t:
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif n == 2:
		if s == s[::-1]:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')
	t -= 1


for i in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeros = n - ones
	if ones >= 2 or zeros >= 2:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline

def solution():
	n = int(input())
	s = input()
	if n > 2:
		print('NO')
	elif n == 1:
		print('YES')
	elif s[0] == s[1]:
		print('NO')
	else:
		print('YES')

def main():
	t = 1
	t = int(input())
	for i in range(t):
		solution()
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n >= 3:
		print('NO')
	elif n == 1 or s in ['01', '10']:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	i = int(input())
	s = input()
	if s.count('1') > 1 or s.count('0') > 1:
		print('NO')
	else:
		print('YES')


for tc in range(int(input())):
	n = int(input())
	st = input()
	if n > 2:
		print('NO')
	elif st.count(st[0]) == 2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = input()
	if n > 2:
		print('NO')
	elif n == 1:
		print('YES')
	elif a[0] != a[1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = len(s)
	if l > 2:
		print('NO')
	elif l == 2:
		if s[0] == '1' and s[1] == '0':
			print('YES')
		elif s[0] == '0' and s[1] == '1':
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())

def solve(s):
	if s == '1' or s == '0' or s == '10' or (s == '01'):
		return 'YES'
	else:
		return 'NO'
for i in range(t):
	n = int(input())
	s = input()
	print(solve(s))


test = int(input())
for t in range(test):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif n > 2:
		print('NO')
	elif s == '11' or s == '00':
		print('NO')
	else:
		print('YES')


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	s = inp().strip()
	if n >= 3:
		print('NO')
	elif n <= 1:
		print('YES')
	elif s[0] != s[1]:
		print('YES')
	else:
		print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())
for _ in range(t):
	x = int(input())
	s = input()
	ss = ''.join(sorted(s))
	if len(ss) == 1:
		print('YES')
	elif ss[0] == ss[1]:
		print('NO')
	elif ss[-1] == ss[-2]:
		print('NO')
	else:
		print('YES')


def solve():
	n = int(input())
	s = input()
	if s == '0' or s == '1' or s == '10' or (s == '01'):
		print('YES')
		return
	print('NO')
	return
for _ in range(int(input())):
	solve()


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if len(s) == 1:
		print('YES')
	elif len(s) > 2:
		print('NO')
	else:
		assert len(s) == 2
		if s[0] == s[1]:
			print('NO')
		else:
			print('YES')


for t in range(int(input())):
	n = int(input())
	s = input()
	ones = 0
	for i in range(n):
		if s[i] == '1':
			ones += 1
	zeros = n - ones
	if n == 1:
		print('YES')
	elif n == 2:
		if ones == 1 and zeros == 1:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	if s in ['0', '1', '10', '01']:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(o, z) = (s.count('1'), s.count('0'))
	if o >= 2 or z >= 2:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt1 = s.count('1')
	cnt0 = s.count('0')
	if n == 1:
		print('YES')
	elif n == 2 and cnt1 == cnt0:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	s = input()
	if n == 1 or s == '01' or s == '10':
		print('YES')
	else:
		print('NO')
tst = int(input())
for tt in range(tst):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	if n > 2:
		print('NO')
		continue
	if s == '11' or s == '00':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	(c1, c2) = (0, 0)
	for i in s:
		if i == '1':
			c1 += 1
		else:
			c2 += 1
	if n == 1:
		print('YES')
	elif n == 2:
		if c1 > c2 or c2 > c1:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
ln = []
strng = []
for i in range(0, t):
	ln.append(int(input()))
	strng.append(str(input()))
for i in range(0, t):
	if ln[i] >= 3:
		print('NO')
	elif ln[i] == 2:
		if strng[i][0] == strng[i][1]:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for x in range(int(input())):
	n = int(input())
	lst = input()
	if n > 2:
		print('NO')
	elif lst == '11' or lst == '00':
		print('NO')
	else:
		print('YES')


t = int(input())
for o in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif n == 2:
		if s[0] == '0' and s[1] == '0' or (s[0] == '1' and s[1] == '1'):
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


inp1 = int(input())
for i in range(inp1):
	inp2 = int(input())
	inp3 = input()
	if len(inp3) >= 3:
		print('NO')
	elif len(inp3) == 2 and inp3[0] == inp3[1]:
		print('NO')
	else:
		print('YES')


no_of_testcases = int(input())
counter = 0
while counter < no_of_testcases:
	size = int(input())
	s = input()
	if size <= 1:
		print('YES')
	elif size > 2:
		print('NO')
	elif s == '11' or s == '00':
		print('NO')
	else:
		print('YES')
	counter += 1


z = int(input())
for q in range(z):
	a = int(input())
	b = input()
	if 2 < a:
		print('NO')
		continue
	if 2 > a:
		print('YES')
		continue
	f = b.count('1')
	if 1 == f:
		print('YES')
	else:
		print('NO')


def checkForPalindorme(s):
	if s == s[::-1]:
		return False
	else:
		return True
n = int(input())
stringLengthList = []
stringList = []
for i in range(n):
	stringLengthList.append(int(input()))
	stringList.append(input())
for i in range(n):
	if stringLengthList[i] < 2:
		print('YES')
	elif stringLengthList[i] == 2:
		if checkForPalindorme(stringList[i]):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def find(arr, n):
	if n >= 3:
		print('NO')
	elif n == 2:
		if arr == '00' or arr == '11':
			print('NO')
		else:
			print('YES')
	else:
		print('YES')
num = int(input())
for i in range(num):
	n = int(input())
	arr = input()
	find(arr, n)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if len(s) == 1:
		print('YES')
		continue
	elif len(s) >= 3:
		print('NO')
	elif len(s) == 2:
		if s[0] == s[1]:
			print('NO')
		else:
			print('YES')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif '00' in s or '11' in s or '101' in s or ('010' in s):
		print('NO')
	else:
		print('YES')


YOUSSEF = int(input())
for loop in range(YOUSSEF):
	n = int(input())
	you = input()
	if you == '1' or you == '0' or you == '10' or (you == '01'):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = s.count('0')
	b = s.count('1')
	if a > 1 or b > 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	l = int(input())
	str = input()
	len(str) - len(set(list(str)))
	if l <= 2 and len(str) - len(set(list(str))) == 0:
		print('YES')
	else:
		print('NO')


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		array = list(s)
		uniquearray = set(array)
		if len(array) == len(uniquearray) and len(array) == 2 or len(array) == 1:
			print('YES')
		else:
			print('NO')
except:
	pass


t = int(input())
while t:
	n = int(input())
	s = str(input())
	if len(s) >= 3:
		print('NO')
	elif s == '00' or s == '11':
		print('NO')
	else:
		print('YES')
	t = t - 1


t = int(input())
for i in range(t):
	l = int(input())
	s = str(input())
	count_0 = 0
	count_1 = 0
	for ch in s:
		if ch == '0':
			count_0 += 1
		else:
			count_1 += 1
	if count_1 > 1 or count_0 > 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	cnt1 = 0
	cnt2 = 0
	for j in s:
		if j == '1':
			cnt1 += 1
		else:
			cnt2 += 1
	if cnt1 <= 1 and cnt2 <= 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	test_str = input()
	if n > 2:
		print('NO')
	elif n == 1:
		print('YES')
	elif test_str[::-1] == test_str:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	if n > 2:
		print('NO')
	else:
		if len(st) == 2:
			if st.count('0') != st.count('1'):
				print('NO')
				continue
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif n == 2:
		if s[0] != s[1]:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


n = int(input())
for i in range(n):
	l = int(input())
	a = input()
	if l > 2:
		print('NO')
	elif l == 1:
		print('YES')
	elif a == '01' or a == '10':
		print('YES')
	else:
		print('NO')


def sum1(a, n):
	for i in range(0, 1 << n):
		s = ''
		for j in range(0, n):
			if i >> j & 1 == 1:
				s = s + a[j]
		if s == s[::-1] and len(s) > 1:
			return 'NO'
	return 'YES'
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = str(input())
	print(sum1(a, n))


for i in range(int(input())):
	k = int(input())
	list1 = input()
	if k > 2:
		print('NO')
	elif k == 2:
		if list1[0] == list1[1]:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


n = int(input())
c = []
for i in range(n):
	a = int(input())
	b = input()
	d = set(b)
	if len(d) == a:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	if n == 1:
		print('YES')
	elif n == 2:
		if s == '00' or s == '11':
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


k = int(input())
for i in range(k):
	m = int(input())
	n = input()
	if n.count('0') > 1 or n.count('1') > 1:
		print('NO')
	else:
		print('YES')


num_test = int(input())
for i in range(num_test):
	n = int(input())
	str1 = str(input())
	if n == 1:
		print('YES')
	elif n == 2 and str1[0] != str1[1]:
		print('YES')
	else:
		print('NO')


t = int(input())
z = []
for _ in range(t):
	n = int(input())
	s = input()
	_0 = 0
	_1 = 0
	for i in s:
		if i == '0':
			_0 += 1
		elif i == '1':
			_1 += 1
	if _0 > 1 or _1 > 1:
		z.append('NO')
	else:
		z.append('YES')
for i in z:
	print(i)


num_cases = int(input())
for i in range(num_cases):
	l = int(input())
	s = input()
	if s.count('1') >= 2 or s.count('0') >= 2:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	ls = int(input())
	s = input()
	if s == '00' or s == '11':
		print('NO')
	elif len(s) <= 2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip()))
	t = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			if len(l[i:j]) == 1:
				pass
			elif l[i:j] == list(reversed(l[i:j])):
				t = 1
				break
		if t == 1:
			print('NO')
			break
	else:
		print('YES')


def funcn(s):
	if s == '1' or s == '0' or s == '10' or (s == '01'):
		print('YES')
	else:
		print('NO')
n = int(input())
while n > 0:
	x = int(input())
	s = str(input())
	funcn(s)
	n -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()

	def isPalindrome(S):
		return S == S[::-1]
	if n > 1 and s != '10' and (s != '01'):
		for j in range(n):
			S = s[j:]
			ans = isPalindrome(S)
			if ans:
				print('NO')
				break
	else:
		print('YES')


t = int(input())
a = '101'
b = '010'
c = '00'
d = '11'
for i in range(0, t):
	n = int(input())
	s = str(input())
	if len(s) <= 2:
		if c in s:
			print('NO')
		elif d in s:
			print('NO')
		else:
			print('YES')
	elif a in s:
		print('NO')
	elif b in s:
		print('NO')
	elif c in s:
		print('NO')
	elif d in s:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = input()
	if a == '1' or a == '0' or a == '10' or (a == '01'):
		print('YES')
	else:
		print('NO')


a = int(input())
otvet = []
for i in range(a):
	aa = int(input())
	if aa > 2:
		aaa = input()
		otvet.append('NO')
	else:
		aaa = input()
		if len(aaa) == 1:
			otvet.append('YES')
		elif aaa[0] != aaa[1]:
			otvet.append('YES')
		else:
			otvet.append('NO')
for i in otvet:
	print(i)