Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given a string $S$ with length $N$. You may perform the following operation any number of times: choose a non-empty substring of $S$ (possibly the whole string $S$) such that each character occurs an even number of times in this substring and erase this substring from $S$. (The parts of $S$ before and after the erased substring are concatenated and the next operation is performed on this shorter string.)

For example, from the string "acabbad", we can erase the highlighted substring "abba", since each character occurs an even number of times in this substring. After this operation, the remaining string is "acd".

Is it possible to erase the whole string using one or more operations?

Note: A string $B$ is a substring of a string $A$ if $B$ can be obtained from $A$ by deleting several (possibly none or all) characters from the beginning and several (possibly none or all) characters from the end.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to erase the whole string or "NO" otherwise (without quotes).

------  Constraints ------
$1 ≤ T ≤ 200$
$1 ≤ N ≤ 1,000$
$S$ contains only lowercase English letters

----- Sample Input 1 ------ 
4

6

cabbac

7

acabbad

18

fbedfcbdaebaaceeba

21

yourcrushlovesyouback
----- Sample Output 1 ------ 
YES

NO

YES

NO
----- explanation 1 ------ 
Example case 1: We can perform two operations: erase the substring "abba", which leaves us with the string "cc", and then erase "cc".

Source: codechef | Difficulty: EASY


Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	st = set(s)
	flag = 0
	l = []
	for i in st:
		l.append(s.count(i))
	for i in range(len(l)):
		if l[i] % 2 != 0:
			flag = flag + 1
	if flag == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	u = set(s)
	flag = True
	if n % 2 != 0:
		print('NO')
	else:
		for i in u:
			if s.count(i) % 2 != 0:
				flag = False
		if flag:
			print('YES')
		else:
			print('NO')


a = int(input())
for i in range(a):
	b = int(input())
	d = input()
	c = 0
	for i in d:
		c = d.count(i)
		if c % 2 == 0:
			c = 0
		else:
			c = 1
			break
	if c != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	A = list(s)
	mp = dict()
	for i in range(n):
		if A[i] in mp.keys():
			mp[A[i]] += 1
		else:
			mp[A[i]] = 1
	flag = 0
	for x in mp.keys():
		if mp.get(x) % 2 != 0:
			flag = 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	my_set = set(s)
	flag = 1
	for i in my_set:
		if s.count(i) % 2 != 0:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')


for T in range(int(input())):
	n = int(input())
	d = input()
	c = 0
	for i in d:
		c = d.count(i)
		if c % 2 == 0:
			c = 0
		else:
			c = 1
			break
	if c != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = [i for i in input()]
	s = set(l)
	(c, o) = ([], 'YES')
	for i in s:
		cn = 0
		for j in l:
			if i == j:
				cn += 1
		c.append(cn)
	for i in c:
		if i % 2 != 0:
			o = 'NO'
	print(o)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	for j in s:
		if s.count(j) % 2 == 0:
			c += 1
		else:
			print('NO')
			break
	if c == n:
		print('YES')


for i in range(int(input())):
	n = int(input())
	lst = [*input()]
	for i in lst:
		if lst.count(i) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


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


t = int(input())
for i in range(t):
	x = int(input())
	lst = list(map(str, input()))
	ans = True
	for j in lst:
		if lst.count(j) % 2 == 0:
			continue
		else:
			ans = False
			break
	if ans == True:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()[:n]
	for i in s:
		if s.count(i) % 2 == 0:
			s = s.replace(i, '')
	if len(s) == 0:
		print('YES')
	else:
		print('NO')


def can_erase_string(s):
	freq = [0] * 26
	for c in s:
		freq[ord(c) - ord('a')] += 1
	for count in freq:
		if count % 2 != 0:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip()
	if can_erase_string(s):
		print('YES')
	else:
		print('NO')


dict = {}
t = int(input())
for i in range(t):
	f = True
	n = int(input())
	s = input()
	for i in range(n):
		dict[s[i]] = 0
	for i in range(n):
		dict[s[i]] += 1
	for i in range(n):
		if dict[s[i]] % 2 != 0:
			f = False
			break
	if f:
		print('YES')
	else:
		print('NO')


def can_erase(s):
	freq = [0] * 26
	for c in s:
		freq[ord(c) - ord('a')] += 1
	for f in freq:
		if f % 2 == 1:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	print(can_erase(s))


for i in range(int(input())):
	n = int(input())
	s = list(input())
	for i in s:
		if s.count(i) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


T = int(input())
for i in range(T):
	B = int(input())
	D = input()
	C = 0
	for i in D:
		C = D.count(i)
		if C % 2 == 0:
			C = 0
		else:
			C = 1
			break
	if C != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	len_string = int(input())
	string = input()
	set_string = set(string)
	if len_string % 2 == 0:
		for alpha in set_string:
			if string.count(alpha) % 2 == 0:
				pass
			else:
				print('NO')
				break
		else:
			print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	str1 = list(input())
	set1 = list(set(str1))
	L1 = [str1.count(i) for i in set1]
	for i in L1:
		if i % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	string1 = list(input())
	set1 = sorted(list(set(string1)))
	L1 = [string1.count(i) for i in set1]
	for i in L1:
		if i % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	N = int(input())
	Str = input()
	s = set(Str)
	flag = 1
	for i in s:
		if Str.count(i) % 2 == 1:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	x = int(input())
	y = input()
	z = 0
	for i in y:
		if y.count(i) % 2 == 1:
			z += 1
	if z != 0:
		print('NO')
	else:
		print('YES')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	k = Counter(s)
	l = k.values()
	r = True
	for i in l:
		if i % 2 == 0:
			continue
		else:
			r = False
	if r:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(input())
	if n % 2 == 1:
		print('NO')
	else:
		for i in set(l):
			if l.count(i) % 2 == 0:
				n -= l.count(i)
		if n == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	x = input()
	unique = set(x)
	list1 = list(unique)
	for j in unique:
		count = x.count(j)
		if count % 2 != 0:
			print('NO')
			break
		elif j == list1[-1]:
			print('YES')
			break


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	x = dict(Counter(s))
	for g in x.values():
		if g % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


cases = int(input())
for case in range(cases):
	length = int(input())
	string = sorted(list(str(input())))
	n = 0
	switch = 1
	if length % 2 == 1:
		switch = 0
	else:
		while n < length:
			if string[n] == string[n + 1]:
				n += 2
				continue
			else:
				switch = 0
				break
	if switch == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	se = set(s)
	for j in se:
		if s.count(j) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = list(s)
	s1 = set(l)
	c = 0
	for i in s1:
		if l.count(i) % 2 != 0:
			print('NO')
			break
		else:
			c += 1
	if c == len(s1):
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	s1 = ''
	m = 0
	for j in s:
		if j not in s1:
			s1 = s1 + j
	for k in s1:
		if s.count(k) % 2 == 0:
			m = m + 1
	if m == len(s1):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	f = 0
	s = list(s)
	k = list(set(s))
	a = []
	for i in k:
		a.append(s.count(i))
	for i in a:
		if i % 2 != 0:
			f = 1
			break
	if f == 1:
		print('NO')
	else:
		print('YES')


def even_reduction(s):
	count = 0
	for i in s:
		if s.count(i) % 2 != 0:
			return 'NO'
		else:
			count += 1
	if count == len(s):
		return 'YES'
T = int(input())
for j in range(T):
	n = int(input())
	s = input()
	print(even_reduction(s))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = list(set(s))
	for i in range(len(c)):
		if s.count(c[i]) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
for i in range(int(input())):
	b = int(input())
	c = input()
	l = []
	for j in c:
		l.append(j)
	s = Counter(l)
	f = 0
	for k in s:
		if s[k] % 2 != 0:
			print('NO')
			f = 1
			break
	if f == 0:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	k = list(s)
	m = []
	c = 0
	for i in s:
		if i not in m:
			m.append(i)
	for i in m:
		p = k.count(i)
		if p % 2 == 0:
			c += 1
	if c == len(m):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	f = 0
	m = int(input())
	st = input()
	l1 = list(st)
	l = list(set(l1))
	for j in range(len(l)):
		if st.count(l[j]) % 2 == 0:
			f = 1
		else:
			f = 0
			break
	if f == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	x = int(input())
	a = input()
	counter = 0
	for i in range(x):
		check = a.count(a[i])
		if check % 2 == 1:
			counter += 1
			break
	if counter == 0:
		print('YES')
	elif counter > 0:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	check = 0
	for j in range(n):
		count = s.count(s[j])
		if count % 2 == 1:
			check = 1
			break
	if check == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	fl = 0
	t = t - 1
	l = int(input())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	for i in d:
		if d[i] % 2 != 0:
			print('NO')
			fl = 1
			break
	if fl == 0:
		print('YES')


for i in range(int(input())):
	a = int(input())
	x = input()
	for j in range(len(x)):
		if x.count(x[j]) % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


aa = int(input())
for i in range(aa):
	bb = int(input())
	dd = input()
	cc = 0
	for i in dd:
		cc = dd.count(i)
		if cc % 2 == 0:
			cc = 0
		else:
			cc = 1
			break
	if cc != 0:
		print('NO')
	else:
		print('YES')


def can_erase_string(s):
	char_count = {}
	for c in s:
		if c in char_count:
			char_count[c] += 1
		else:
			char_count[c] = 1
	for count in char_count.values():
		if count % 2 == 1:
			return False
	return True
for i in range(int(input())):
	a = int(input())
	b = input()
	if can_erase_string(b):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = int(input())
	lst = list(input())
	lst1 = list(set(lst))
	L1 = [lst.count(i) for i in lst1]
	for i in L1:
		if i % 2 != 0:
			print('NO')
			break
	else:
		print('YES')


n = int(input())
for _ in range(n):
	n1 = int(input())
	s = [a for a in input()]
	s1 = list(set(s))
	c = []
	for i in s1:
		x = s.count(i)
		if x % 2 == 0:
			c.append(0)
		else:
			c.append(1)
	c1 = list(set(c))
	if len(c1) == 1 and c1[0] == 0:
		print('YES')
	else:
		print('NO')


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