Chef has a string A (containing lowercase Latin letters only) of length N where N is even. He can perform the following operation any number of times:
Swap A_{i} and A_{i + 2} for any 1 ≤ i ≤ (N - 2)

Determine if Chef can convert string A to a palindromic string.

Note: A string is called a palindrome if it reads the same backwards and forwards. For example, \texttt{noon} and \texttt{level} are palindromic strings but \texttt{ebb} is not.

------ 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 length of the string A.
- The second line of each test case contains a string A of length N containing lowercase Latin letters only.

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

For each test case, output YES if Chef can convert the string A to a palindromic string. Otherwise, output NO.

You may print each character of YES and NO in either uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

$1 ≤ T ≤ 200$
$1 ≤ N ≤ 1000$
$S$ contains lowercase Latin letters only.
$N$ is even

----- Sample Input 1 ------ 
3
6
aabbaa
4
abcd
6
zzxyyx

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

----- explanation 1 ------ 
Test case $1$: The given string is already a palindrome.

Test case $2$: It can be proven that is it not possible to convert $A$ to a palindromic string.

Test case $3$: We can perform the following operations:
- Swap $A_{1}$ and $A_{3}$. (Now $A$ becomes xzzyyx)
- Swap $A_{2}$ and $A_{4}$. (Now $A$ becomes xyzzyx)

Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
from collections import Counter
t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	s1 = list(s[0::2])
	s2 = list(s[1::2])
	s1.sort()
	s2.sort()
	if s1 == s2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(input())
	e = l[::2]
	o = l[1::2]
	e.sort()
	o.sort()
	if e == o:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	(s1, s2) = ('', '')
	for i in range(n):
		if i % 2:
			s1 += s[i]
		else:
			s2 += s[i]
	ans = 'YES'
	(s1, s2) = (dict(Counter(s1)), dict(Counter(s2)))
	for (x, y) in s1.items():
		if s2.get(x, 0) != y:
			ans = 'NO'
			break
	if ans == 'YES':
		for (x, y) in s2.items():
			if s1.get(x, 0) != y:
				ans = 'NO'
				break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	e = sorted(s[:n:2])
	o = sorted(s[1:n:2])
	if e == o:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = input().strip()
	evens = sorted(A[:N:2])
	odds = sorted(A[1:N:2])
	if evens == odds:
		print('YES')
	else:
		print('NO')


output = ''
for _ in range(int(input())):
	n = int(input())
	word = input()
	even = ''
	odd = ''
	for i in range(n):
		if i % 2 == 0:
			even += word[i]
		else:
			odd += word[i]
	even = ''.join(sorted(even))
	odd = ''.join(sorted(odd))
	if even == odd:
		output += 'YES' + '\n'
	else:
		output += 'NO' + '\n'
print(output)


for tc in range(int(input())):
	n = int(input())
	arr = list(input())
	evens = sorted(arr[::2])
	odds = sorted(arr[1::2])
	if evens == odds:
		print('YES')
	else:
		print('NO')


testcase = int(input())
for _ in range(testcase):
	N = int(input())
	arr = input()
	even_str = list(arr[::2])
	odd_str = list(arr[1::2])
	even_str.sort()
	odd_str.sort()
	if even_str == odd_str:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	s1 = list(s[::2])
	s2 = list(s[1::2])
	s1.sort()
	s2.sort()
	if s1 == s2:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	string = input()
	even_index = list(string[::2])
	odd_index = list(string[1::2])
	even_index.sort()
	odd_index.sort()
	if even_index == odd_index:
		print('YES')
	else:
		print('NO')


t = int(input(''))
if 1 <= t <= 200:
	for _ in range(t):
		n = int(input(''))
		s = input('')
		z = 0
		if len(s) == n and 1 <= n <= 1000 and (n % 2 == 0):
			final = 0
			s1 = []
			for i in range(n - 1):
				x = s[i]
				if x not in s1:
					s1.append(x)
					e = o = 0
					if i % 2 == 0:
						e += 1
					else:
						o += 1
					for j in range(i + 1, n):
						if s[j] == x:
							if j % 2 == 0:
								e += 1
							else:
								o += 1
					if e != o:
						print('NO')
						break
					else:
						z += 1
			if z == len(s1):
				print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	d = dict.fromkeys(s, 0)
	for i in s:
		d[i] += 1
	for i in d:
		if d[i] & 1 == 1:
			print('NO')
			break
	else:
		dt = {}
		i1 = 0
		for i in s:
			if i not in dt:
				dt.update({i: [i1]})
			else:
				m = list(dt[i])
				m.append(i1)
				dt[i] = m
			i1 += 1
		for i in dt:
			e = 0
			o = 0
			for j in dt[i]:
				if j & 1 == 0:
					e += 1
				else:
					o += 1
			if e != o:
				print('NO')
				break
		else:
			print('YES')


for i in range(int(input())):
	a = int(input())
	b = input()
	li = []
	li2 = []
	for i in range(len(b)):
		if i % 2 == 0:
			li.append(b[i])
		else:
			li2.append(b[i])
	li.sort()
	li2.sort()
	if li == li2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	even = list(s[::2])
	odd = list(s[1::2])
	even.sort()
	odd.sort()
	if even == odd:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	stri = input()
	l1 = []
	l2 = []
	for i in range(n):
		if i % 2 == 0:
			l1.append(stri[i])
		else:
			l2.append(stri[i])
	l1.sort()
	l2.sort()
	if l1 == l2:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if sorted((ch for (i, ch) in enumerate(s) if i & 1 == 0)) == sorted((ch for (i, ch) in enumerate(s) if i & 1)):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	o = ''
	e = ''
	for i in range(n):
		if i & 1:
			o = o + a[i]
		else:
			e = e + a[i]
	o = list(o)
	o.sort()
	e = list(e)
	e.sort()
	if o == e:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	N = int(input())
	A = input()
	C = Counter(A)
	(A1, A2) = ([], [])
	for i in range(N):
		if i % 2:
			A1.append(A[i])
		else:
			A2.append(A[i])
	(C1, C2) = (Counter(A1), Counter(A2))
	ans = 'YES'
	for i in C:
		if C[i] % 2:
			ans = 'NO'
			break
		elif i not in C1 or i not in C2:
			ans = 'NO'
			break
		elif C1[i] != C2[i]:
			ans = 'NO'
			break
	print(ans)


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


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	A = [a for a in s[::2]]
	B = [a for a in s[1::2]]
	A.sort()
	B.sort()
	if A == B:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	num = int(input())
	A = str(input())
	print('YES' if sorted(A[::2]) == sorted(A[1::2]) else 'NO')
	t -= 1


for t in range(int(input())):
	n = int(input())
	a = list(input())
	eA = []
	oA = []
	for i in range(n):
		if i % 2 == 0:
			eA.append(a[i])
		else:
			oA.append(a[i])
	eA.sort()
	oA.sort()
	if eA == oA:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	d1 = {}
	d2 = {}
	flag = 1
	for i in range(n):
		if i % 2 == 0:
			if d1.get(s1[i]) is None:
				d1[s1[i]] = 1
			else:
				d1[s1[i]] += 1
		elif d2.get(s1[i]) is None:
			d2[s1[i]] = 1
		else:
			d2[s1[i]] += 1
	for i in range(n):
		if d1.get(s1[i]) is not None and d2.get(s1[i]) is not None:
			if d1[s1[i]] != d2[s1[i]]:
				flag = 0
				break
		else:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	print('YES' if sorted(A[::2]) == sorted(A[1::2]) else 'NO')


from collections import Counter
T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	print('YES' if Counter(A[::2]) == Counter(A[1::2]) else 'NO')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	l1 = []
	l2 = []
	for i in range(n):
		if i % 2 == 0:
			l1.append(s[i])
		else:
			l2.append(s[i])
	l1.sort()
	l2.sort()
	if l1 == l2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	even = [0] * 26
	odd = [0] * 26
	for i in range(len(s)):
		if i % 2 == 0:
			even[ord(s[i]) - ord('a')] += 1
		else:
			odd[ord(s[i]) - ord('a')] += 1
	if even == odd:
		print('YES')
	else:
		print('NO')


import collections as clts
import math
import heapq

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)

def take_input(type='list-int'):
	if type == 'list-int':
		return list(map(int, input().split()))
	elif type == 'list-float':
		return list(map(float, input().split()))
	else:
		return None
for _ in range(int(input())):
	N = int(input())
	A = input()
	charMap = clts.defaultdict(list)
	for i in range(N):
		if len(charMap[A[i]]) == 0:
			charMap[A[i]].append(i)
		else:
			index = charMap[A[i]].pop()
			if index % 2 == 0 and i % 2 != 0 or (index % 2 != 0 and i % 2 == 0):
				continue
			else:
				charMap[A[i]].extend([index, i])
	possible = True
	for ind in charMap.values():
		if len(ind) != 0:
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


def test():
	len_S = int(input())
	S = str(input())
	lst_odd = [0] * 26
	lst_even = [0] * 26
	for i in range(len_S):
		if i % 2 == 0:
			lst_even[ord(S[i]) - ord('a')] += 1
		else:
			lst_odd[ord(S[i]) - ord('a')] += 1
	if lst_even == lst_odd:
		print('YES')
	else:
		print('NO')
tests = int(input())
for i in range(tests):
	test()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s1 = []
	s1[:0] = s
	(a, b) = ([], [])
	for i in range(n):
		if i % 2 == 0:
			a.append(s1[i])
		else:
			b.append(s1[i])
	a.sort()
	b.sort()
	flag = 0
	for i in range(n // 2):
		if a[i] != b[i]:
			flag = 1
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


for testcase in range(int(input())):
	n = int(input())
	string = input()
	counter = {}
	for i in range(n):
		if i % 2:
			counter[string[i]] = counter[string[i]] + 1 if string[i] in counter else 1
		else:
			counter[string[i]] = counter[string[i]] - 1 if string[i] in counter else -1
	for i in counter:
		if counter[i]:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	temp = a[::2]
	temp1 = a[1::2]
	if sorted(temp) == sorted(temp1):
		print('YES')
	else:
		print('NO')


def pal(arr):
	s = set(arr)
	ctr = 0
	for i in s:
		if arr.count(i) % 2 != 0:
			ctr = 1
			return 'NO'
			break
	if ctr == 0:
		g1 = list(arr[::2])
		g2 = list(arr[1::2])
		g1.sort()
		g2.sort()
		if g1 == g2:
			return 'YES'
		else:
			return 'NO'
for i in range(int(input())):
	n = int(input())
	a = input()
	if a[::-1] == a:
		print('YES')
	elif len(set(a)) > len(a) // 2:
		print('NO')
	else:
		print(pal(a))


def solve():
	N = int(input())
	S = input()
	f = [0 for i in range(26)]
	for i in range(N):
		k = ord(S[i]) - ord('a')
		if i % 2 == 0:
			f[k] += 1
		else:
			f[k] -= 1
	for i in range(26):
		if f[i] != 0:
			print('NO')
			return
	print('YES')

def main():
	T = int(input())
	while T > 0:
		solve()
		T = T - 1
main()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	od_ch = defaultdict(int)
	ev_ch = defaultdict(int)
	for c in s[::2]:
		od_ch[c] += 1
	for c in s[1::2]:
		ev_ch[c] += 1
	ans = 'YES'
	if n == 1:
		pass
	elif n % 2 != 0:
		ans = all((cn % 2 == 0 for cn in ev_ch))
		ans = ans and len(filter((lambda cn: cn % 2 != 0 for cn in od_ch))) == 1
	else:
		ans = all((od_ch.get(ch, 0) == ev_ch.get(ch, 0) for ch in ev_ch))
	print('YES' if ans else 'NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	es = [0 for i in range(26)]
	os = [0 for i in range(26)]
	check = True
	for i in range(0, n, 2):
		es[ord(s[i]) - 96 - 1] += 1
	for i in range(1, n, 2):
		os[ord(s[i]) - 96 - 1] += 1
	for i in range(26):
		if es[i] != os[i]:
			check = False
	if check:
		print('YES')
	else:
		print('NO')


import collections
t = int(input())
while t != 0:
	e = ''
	o = ''
	n = int(input())
	s = input()
	for i in range(n):
		if i % 2 != 0:
			o += s[i]
		else:
			e += s[i]
	x = collections.Counter(e)
	y = collections.Counter(o)
	if x == y:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lst1 = []
	lst2 = []
	for i in range(n):
		if i % 2 == 0:
			lst1.append(s[i])
		else:
			lst2.append(s[i])
	lst1.sort()
	lst2.sort()
	if lst1 == lst2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l1 = []
	l2 = []
	for i in range(n):
		if i & 1 == 0:
			l1.append(s[i])
		else:
			l2.append(s[i])
	l1.sort()
	l2.sort()
	if l1 == l2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	a = ''
	b = ''
	for j in range(0, n, 2):
		a += l[j]
	for j in range(1, n, 2):
		b += l[j]
	a = sorted(a)
	b = sorted(b)
	if a == b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	s = input()
	a = []
	b = []
	for i in range(N):
		if i % 2 == 0:
			a.append(s[i])
		else:
			b.append(s[i])
	a.sort()
	b.sort()
	if a == b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	e = []
	o = []
	for i in range(len(s)):
		if i % 2 == 0:
			e.append(s[i])
		else:
			o.append(s[i])
	if sorted(e) == sorted(o):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	(eve_ind, odd_ind) = ([], [])
	for i in range(n):
		if i % 2 == 0:
			eve_ind.append(s[i])
		else:
			odd_ind.append(s[i])
	eve_ind.sort()
	odd_ind.sort()
	if eve_ind == odd_ind:
		print('YES')
	else:
		print('NO')


def solve(x):
	if x == x[::-1]:
		print('YES')
		return
	s1 = ''
	s2 = ''
	for i in range(len(x)):
		if i % 2 == 0:
			s2 += x[i]
			continue
		s1 += x[i]
	if sorted(s1) == sorted(s2):
		print('YES')
		return
	print('NO')
	return
x = int(input())
for i in range(x):
	y = input()
	z = input()
	solve(z)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	b = []
	c = []
	for i in range(n):
		if i % 2 == 0:
			b.append(s[i])
		else:
			c.append(s[i])
	b.sort()
	c.sort()
	if b == c:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	x = list(input())
	y = []
	z = []
	for i in range(n):
		if i % 2 == 0:
			y.append(x[i])
		else:
			z.append(x[i])
	y.sort()
	z.sort()
	if y == z:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	x = int(input())
	s = list(input())
	a = []
	b = []
	for j in range(x):
		if j % 2 == 0:
			a.append(s[j])
		else:
			b.append(s[j])
	a.sort()
	b.sort()
	if a == b:
		print('YES')
	else:
		print('NO')


def pal(s, n):
	od = []
	ev = []
	for i in range(0, n, 2):
		od.append(s[i])
	for i in range(1, n, 2):
		ev.append(s[i])
	return sorted(ev) == sorted(od)
n = int(input())
for i in range(n):
	k = int(input())
	st = input()
	if pal(st, k):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	(N, A) = (int(input()), input())
	symb_even = sorted(''.join([A[j] for j in range(N) if j % 2 == 0]))
	symb_odd = sorted(''.join([A[j] for j in range(N) if j % 2 != 0]))
	print('YES' if symb_even == symb_odd else 'NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	m = []
	k = []
	for i in range(n):
		if i % 2 == 0:
			m.append(s[i])
		else:
			k.append(s[i])
	m.sort()
	k.sort()
	if m == k:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if s[:] == s[::-1]:
		print('YES')
	else:
		a = sorted(s[::2])
		b = sorted(s[1::2])
		if a == b:
			print('YES')
		else:
			print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = str(input())
	s1 = ''
	s2 = ''
	for i in range(0, N, 2):
		s1 += A[i]
	for i in range(1, N + 1, 2):
		s2 += A[i]
	if sorted(s1) == sorted(s2):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = str(input())
	grp_1 = ''
	grp_2 = ''
	for i in range(0, len(A), 2):
		grp_1 += A[i]
	for i in range(1, len(A) + 1, 2):
		grp_2 += A[i]
	if sorted(grp_1) == sorted(grp_2):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	i = int(input())
	string = input()
	l1 = [string[x - 1] for x in range(1, i + 1) if x % 2 == 0]
	l2 = [string[x - 1] for x in range(1, i + 1) if x % 2 != 0]
	print('YES') if sorted(l1) == sorted(l2) else print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l1 = [s[i - 1] for i in range(1, n + 1) if i % 2 == 0]
	l2 = [s[i - 1] for i in range(1, n + 1) if i % 2 != 0]
	if sorted(l1) == sorted(l2):
		print('YES')
	else:
		print('NO')


t = int(input())

def Func():
	n = int(input())
	s = input()
	ls = [i for i in s]
	sett = set(ls)
	list1 = []
	list2 = []
	check = 1
	if len(ls) % 2 == 0:
		for j in sett:
			if ls.count(j) % 2 != 0:
				check = 0
		if check == 1:
			for i in range(0, len(ls), 2):
				list1.append(ls[i])
			for i in range(1, len(ls), 2):
				list2.append(ls[i])
			if sorted(list1) == sorted(list2):
				return 'YES'
			else:
				return 'NO'
		else:
			return 'NO'
	else:
		return 'NO'
for i in range(t):
	print(Func())


t = int(input())
for i in range(t):
	n = int(input())
	string = input()[:n]
	odd = ''
	even = ''
	for i in range(len(string)):
		if i % 2 == 0:
			even += string[i]
		else:
			odd += string[i]
	sortedEven = ''.join(sorted(even))
	sortedOdd = ''.join(sorted(odd))
	if sortedEven == sortedOdd:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	p = sorted(s[::2])
	q = sorted(s[1::2])
	print('YES' if p == q else 'NO')


for i in range(int(input())):
	n = int(input())
	s = list(input())
	l1 = []
	l2 = []
	for i in range(0, n):
		if i % 2 == 0:
			l1.append(s[i])
		else:
			l2.append(s[i])
	l1.sort()
	l2.sort()
	f = 0
	for i in range(0, len(l1)):
		if l1[i] != l2[i]:
			print('NO')
			f = 1
			break
	if f == 0:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = input()
	even = []
	odd = []
	for i in range(n):
		if i % 2 == 0:
			even.append(a[i])
		else:
			odd.append(a[i])
	flag = 0
	for i in even:
		if even.count(i) != odd.count(i):
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


cnt = int(input())
for i in range(cnt):
	j = int(input())
	str = input()
	even = ''
	odd = ''
	for k in range(0, j, 2):
		even = even + str[k]
		odd = odd + str[k + 1]
	for c in even:
		odd = odd.replace(c, '', 1)
	if len(odd) == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
from collections import Counter
while t:
	n = int(input())
	s = list(input().strip(' '))
	s1 = []
	s2 = []
	for i in range(0, n):
		if i % 2 == 0:
			s1.append(s[i])
		else:
			s2.append(s[i])
	flag = 0
	for i in s1:
		if s1.count(i) != s2.count(i):
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')
	t -= 1