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

You are given a string $S$ with length $N$ and you should change it to a palindrome using a sequence of zero or more operations. In one operation, you should choose two adjacent elements of $S$ (two characters) and swap them; however, neither of these elements may be used in any other operation.

Find the minimum number of operations you have to perform in order to change the string $S$ into a palindrome, or determine that it is impossible.

------  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:
If it is impossible to make the string $S$ a palindrome, print a single line containing the string "NO" (without quotes).
Otherwise, print two lines. The first of these lines should contain the string "YES" (without quotes). The second line should contain a single integer ― the minimum required number of operations.

------  Constraints ------
$1 ≤ T ≤ 10,000$
$1 ≤ N ≤ 10^{5}$
$S$ contains only lowercase English letters
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$N ≤ 10^{3}$
$S$ contains only characters 'a' and 'b'
the sum of $N$ over all test cases does not exceed $10^{4}$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
3

4

abab

5

acbba

5

aaaab
----- Sample Output 1 ------ 
YES

1

YES

1

NO

Difficulty: HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	(i, j) = (0, n - 1)
	count = 0
	flag = 0
	(bl, br) = (0, 0)
	s = list(s)
	while i < n and j >= 0 and (i < j):
		if s[i] != s[j]:
			if i + 1 == j:
				flag += 1
				print('NO')
				break
			elif br == 0 and s[i] == s[j - 1]:
				(s[j - 1], s[j]) = (s[j], s[j - 1])
				count += 1
				(bl, br) = (0, 1)
			elif bl == 0 and s[i + 1] == s[j]:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				count += 1
				(bl, br) = (1, 0)
			else:
				flag += 1
				print('NO')
				break
		else:
			(bl, br) = (0, 0)
		i += 1
		j -= 1
	if flag == 0:
		print('YES')
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = list(s)
	i = 0
	j = n - 1
	mop = 0
	f = 0
	(bl, br) = (0, 0)
	while i < j:
		if s[i] != s[j]:
			if i + 1 == j:
				f += 1
				break
			elif s[i + 1] == s[j] and bl == 0:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				mop += 1
				(bl, br) = (1, 0)
			elif s[i] == s[j - 1] and br == 0:
				(s[j], s[j - 1]) = (s[j - 1], s[j])
				mop += 1
				(bl, br) = (0, 1)
			else:
				f = 1
				break
		else:
			(bl, br) = (0, 0)
		i += 1
		j -= 1
	if f:
		print('NO')
	else:
		print('YES')
		print(mop)


for u in range(int(input())):
	n = int(input())
	s = list(input())
	l = [0 for i in range(n)]
	(i, j) = (0, n - 1)
	c = 0
	f = 0
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] == s[j - 1] and l[j] == 0 and (l[j - 1] == 0):
			(s[j], s[j - 1]) = (s[j - 1], s[j])
			l[j] = 1
			l[j - 1] = 1
			i += 1
			j -= 1
			c += 1
		elif s[i + 1] == s[j] and l[i] == 0 and (l[i + 1] == 0):
			(s[i + 1], s[i]) = (s[i], s[i + 1])
			l[i] = 1
			l[i + 1] = 1
			i += 1
			j -= 1
			c += 1
		else:
			break
	for i in range(n // 2 + 1):
		if s[i] != s[n - i - 1]:
			f = 1
			break
	if f == 1:
		print('NO')
	else:
		print('YES')
		print(c)


from collections import defaultdict
from heapq import *
for _ in range(int(input())):
	n = int(input())
	s = input()
	s = list(s)
	(i, j) = (0, n - 1)
	k = 0
	flag = 1
	(l, r) = (1, 1)
	if n == 1:
		print('YES')
		print(k)
		continue
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			(l, r) = (1, 1)
		elif j - 1 != i and s[i] == s[j - 1] and r:
			(s[j - 1], s[j]) = (s[j], s[j - 1])
			i += 1
			j -= 1
			k += 1
			(r, l) = (0, 1)
		elif i + 1 != j and s[i + 1] == s[j] and l:
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			i += 1
			j -= 1
			k += 1
			(l, r) = (0, 1)
		else:
			print('NO')
			flag = 0
			break
	if flag:
		print('YES')
		print(k)


T = int(input())
for i in range(T):
	n = int(input())
	a = input()
	s = []
	for i in range(n):
		s.append(a[i])
	k = (n - 1) // 2
	f = 1
	i = 0
	j = n - 1
	p = [0] * n
	c = 0
	while i <= k:
		if s[i] != s[j]:
			if i < k and p[i] == 0 and (s[i + 1] == s[j]):
				t = s[i + 1]
				s[i + 1] = s[i]
				s[i] = t
				p[i + 1] = 1
				c += 1
			elif i < k and p[j] == 0 and (s[j - 1] == s[i]):
				t = s[j - 1]
				s[j - 1] = s[j]
				s[j] = t
				p[j - 1] = 1
				c += 1
			else:
				f = 0
				break
		i += 1
		j -= 1
	if f == 0:
		print('NO')
	else:
		print('YES')
		print(c)


def test():
	n = int(input())
	a = list(input())
	hn = n // 2
	c = 0
	used = [False for i in range(n)]
	for low in range(hn + 1):
		high = n - 1 - low
		if a[low] == a[high]:
			used[low] = True
			used[high] = True
			continue
		if low < hn and a[low + 1] == a[high] and (not used[low]) and (not used[low + 1]):
			used[high] = True
			used[low + 1] = True
			used[low] = True
			(a[low], a[low + 1]) = (a[low + 1], a[low])
			c += 1
			continue
		if low < hn and a[low] == a[high - 1] and (not used[high - 1]) and (not used[high]):
			used[low] = True
			used[high - 1] = True
			used[high] = True
			(a[high], a[high - 1]) = (a[high - 1], a[high])
			c += 1
			continue
		print('NO')
		return
	print('YES')
	print(c)
for _ in range(int(input())):
	test()


from math import ceil
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	S = list(input())
	move = [True for i in range(N)]
	count = 0
	for i in range(ceil(N / 2)):
		if S[i] != S[N - i - 1]:
			if move[i] and i + 1 != N - i - 1 and (S[i + 1] == S[N - i - 1]):
				(S[i], S[i + 1]) = (S[i + 1], S[i])
				move[i + 1] = False
				count += 1
			elif move[N - i - 1] and N - i - 2 != i and (S[i] == S[N - i - 2]):
				(S[N - i - 1], S[N - i - 2]) = (S[N - i - 2], S[N - i - 1])
				move[N - i - 2] = False
				count += 1
			else:
				count = -1
				break
	if count == -1:
		ans.append('NO')
	else:
		ans.append('YES')
		ans.append(count)
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	(ans, flag) = (0, 0)
	(a, b) = (0, n - 1)
	(l, r) = (0, 0)
	if n == 2:
		if s[0] != s[1]:
			print('NO')
		else:
			print('YES')
			print(0)
	else:
		while a < b:
			if s[a] == s[b]:
				(l, r) = (0, 0)
			elif a + 1 == b:
				print('NO')
				flag = 1
				break
			elif s[a + 1] == s[b] and l == 0:
				temp = s[a]
				s[a] = s[a + 1]
				s[a + 1] = temp
				(l, r) = (1, 0)
				ans += 1
			elif s[a] == s[b - 1] and r == 0:
				temp = s[b]
				s[b] = s[b - 1]
				s[b - 1] = temp
				(l, r) = (0, 1)
				ans += 1
			else:
				print('NO')
				flag = 1
				break
			a += 1
			b -= 1
		if flag == 0:
			print('YES')
			print(ans)


import sys
from collections import defaultdict

def fin():
	return sys.stdin.readline().strip()

def fout(s, end='\n'):
	sys.stdout.write(str(s) + end)
test = int(input())
for _ in range(test):
	n = int(input())
	s = list(fin())
	ans = i = 0
	j = n - 1
	left = right = False
	while i < j:
		if s[i] == s[j]:
			left = right = False
			pass
		elif i + 1 < j:
			if s[j - 1] == s[i] and (not right):
				(s[j - 1], s[j]) = (s[j], s[j - 1])
				ans += 1
				left = False
				right = True
			elif s[i + 1] == s[j] and (not left):
				(s[i + 1], s[i]) = (s[i], s[i + 1])
				ans += 1
				left = True
				right = False
			elif i + 1 != j - 1 and s[i + 1] == s[j - 1] and (not right) and (not left):
				(s[i + 1], s[i]) = (s[i], s[i + 1])
				(s[j - 1], s[j]) = (s[j], s[j - 1])
				ans += 2
				left = right = True
			else:
				ans = -1
				break
		else:
			ans = -1
			break
		i += 1
		j -= 1
	if ans == -1:
		print('NO')
	else:
		print('YES')
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	(l, r) = (0, n - 1)
	rightSwap = 0
	leftSwap = 0
	ans = 0
	flag = 1
	while l < r:
		if s[l] != s[r]:
			if l + 1 == r:
				flag = 0
				print('NO')
				break
			elif s[l] == s[r - 1] and rightSwap == 0:
				(s[r - 1], s[r]) = (s[r], s[r - 1])
				rightSwap = 1
				leftSwap = 0
				ans += 1
			elif s[l + 1] == s[r] and leftSwap == 0:
				(s[l + 1], s[l]) = (s[l], s[l + 1])
				leftSwap = 1
				rightSwap = 0
				ans += 1
			else:
				print('NO')
				flag = 0
				break
		else:
			leftSwap = 0
			rightSwap = 0
		l += 1
		r -= 1
	if flag:
		print('YES')
		print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	L = list(S)
	l = 0
	r = N - 1
	c = 0
	i = 0
	flag = 0
	right_check = 0
	left_check = 0
	while l < r:
		if L[l] != L[r]:
			if l + 1 == r:
				flag = 1
				print('NO')
				break
			elif L[l] == L[r - 1] and right_check == 0:
				(L[r - 1], L[r]) = (L[r], L[r - 1])
				right_check = 1
				left_check = 0
				c += 1
			elif L[l + 1] == L[r] and left_check == 0:
				(L[l], L[l + 1]) = (L[l + 1], L[l])
				left_check = 1
				right_check = 0
				c += 1
			else:
				print('NO')
				flag = 1
				break
		else:
			left_check = 0
			right_check = 0
		l += 1
		r -= 1
	if flag == 0:
		print('YES')
		print(c)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	op = 0
	t = ceil(n / 2) - 1
	swap = 2
	m = n - 1
	flag = 0
	for i in range(t):
		if s[i] != s[m - i]:
			if s[i] == s[m - i - 1] and swap != 0:
				temp = s[m - i]
				s[m - i] = s[m - i - 1]
				s[m - i - 1] = temp
				swap = 0
				op = op + 1
			elif s[i + 1] == s[m - i] and swap != 1:
				temp = s[i]
				s[i] = s[i + 1]
				s[i + 1] = temp
				swap = 1
				op = op + 1
			else:
				flag = 1
				break
		else:
			swap = 2
	if n % 2 == 0:
		if s[int(n / 2)] != s[int(n / 2) - 1]:
			flag = 1
	if flag == 0:
		print('YES')
		print(op)
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	word = input()
	word = list(word)
	left = 0
	right = n - 1
	swapped = [False] * len(word)
	flag = True
	while left < right:
		if word[left] != word[right]:
			if left + 1 == right:
				flag = False
				break
			if not swapped[left] and word[left + 1] == word[right]:
				(word[left], word[left + 1]) = (word[left + 1], word[left])
				swapped[left] = True
				swapped[left + 1] = True
			elif not swapped[right] and word[right - 1] == word[left]:
				(word[right], word[right - 1]) = (word[right - 1], word[right])
				swapped[right] = True
				swapped[right - 1] = True
			else:
				flag = False
				break
		left += 1
		right -= 1
	if flag:
		print('YES')
		print(swapped.count(True) // 2)
	else:
		print('NO')


def validate(l):
	j = 0
	k = n - 1
	c = 0
	li = [-1] * n
	while j < k:
		if l[j] != l[k]:
			if li[j] != -1 and li[k] != -1:
				return False
			if li[j] != -1:
				if l[k - 1] == l[j] and k - 1 != j:
					c += 1
					(l[k], l[k - 1]) = (l[k - 1], l[k])
					li[k] = 0
					li[k - 1] = 0
				else:
					return False
			elif li[k] != -1:
				if l[k] == l[j + 1] and k != j + 1:
					c += 1
					(l[j], l[j + 1]) = (l[j + 1], l[j])
					li[j] = 0
					li[j + 1] = 0
				else:
					return False
			elif l[k - 1] == l[j] and k - 1 != j:
				c += 1
				(l[k], l[k - 1]) = (l[k - 1], l[k])
				li[k] = 0
				li[k - 1] = 0
			elif l[k] == l[j + 1] and k != j + 1:
				c += 1
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				li[j] = 0
				li[j + 1] = 0
			else:
				return False
		j += 1
		k -= 1
	print('YES')
	print(c)
	return True
for _ in range(int(input())):
	n = int(input())
	l = list(input())
	if not validate(l):
		print('NO')


for test in range(int(input())):
	n = int(input())
	s = 'abcd'
	if n != 0:
		s = input()
	l = list(s)
	(i, j) = (0, n - 1)
	count = 0
	for i in range(int(n / 2)):
		if i == j or n < 3:
			break
		elif l[i] == l[j]:
			j -= 1
			continue
		elif l[i] == l[j - 1]:
			c = l[j]
			l[j] = l[j - 1]
			l[j - 1] = c
			count += 1
			if l[i + 1] != l[j - 1] and l[i + 2] != l[j - 1]:
				break
			j -= 1
			continue
		elif l[i + 1] == l[j]:
			c = l[i]
			l[i] = l[i + 1]
			l[i + 1] = c
			count += 1
			if l[i + 1] != l[j - 1] and l[j - 2] != l[i + 1]:
				break
			j -= 1
			continue
	if l == l[-1::-1]:
		print('YES')
		print(count)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	if n == 1:
		print('YES')
		print(0)
	elif n == 2:
		if s[0] == s[1]:
			print('YES')
			print(0)
		else:
			print('NO')
	else:
		l = 0
		r = n - 1
		ans = 0
		vis = [0] * n
		while True:
			if l + 1 == r:
				if s[l] != s[r]:
					print('NO')
					break
				else:
					print('YES')
					print(ans)
					break
			elif l == r:
				print('YES')
				print(ans)
				break
			elif s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] != s[r]:
				if s[l + 1] == s[r] and vis[l + 1] == 0 and (vis[l] == 0):
					(s[l + 1], s[l]) = (s[l], s[l + 1])
					ans += 1
					vis[l + 1] = vis[l] = 1
					l += 1
					r -= 1
				elif s[l] == s[r - 1] and vis[r] == 0 and (vis[r - 1] == 0):
					(s[r], s[r - 1]) = (s[r - 1], s[r])
					ans += 1
					vis[r] = vis[r - 1] = 1
					l += 1
					r -= 1
				else:
					print('NO')
					break


t = int(input())
while t:
	t = t - 1
	n = int(input())
	li = list(input())
	justSwapped = -1
	yes = True
	count = 0
	for i in range(n // 2):
		flag = 0
		endi = n - 1 - i
		if li[i] == li[endi]:
			justSwapped = -1
			continue
		else:
			if justSwapped != i:
				if i + 1 <= (n - 1) // 2 and li[i + 1] == li[endi]:
					flag = 1
					temp = li[i]
					li[i] = li[i + 1]
					li[i + 1] = temp
					justSwapped = i + 1
					count += 1
			if flag == 0 and justSwapped != endi:
				if endi - 1 >= n // 2 and li[endi - 1] == li[i]:
					flag = 1
					temp = li[endi]
					li[endi] = li[endi - 1]
					li[endi - 1] = temp
					justSwapped = endi - 1
					count += 1
			if flag == 0:
				print('NO')
				yes = False
				break
	if yes:
		print('YES')
		print(count)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	sl = list(s)
	i = 0
	j = len(s) - 1
	swapi = 0
	swapj = 0
	flag = 0
	count = 0
	enter = 0
	while i < j:
		if sl[i] == sl[j]:
			i += 1
			j -= 1
			swapi = 0
			swapj = 0
			continue
		elif i + 1 == j and sl[i] != sl[j]:
			flag = 1
			break
		elif sl[i] == sl[j - 1] and swapj != 1:
			(sl[j], sl[j - 1]) = (sl[j - 1], sl[j])
			i += 1
			j -= 1
			swapj = 1
			swapi = 0
		elif sl[i + 1] == sl[j] and swapi != 1:
			(sl[i], sl[i + 1]) = (sl[i + 1], sl[i])
			i += 1
			j -= 1
			swapi = 1
			swapj = 0
		else:
			flag = 1
			break
		count += 1
	if flag == 1:
		print('NO')
	else:
		print('YES')
		print(count)
	t -= 1


t = int(input())
while t:
	n = int(input())
	s = input()
	r = n - 1
	str_list = list(s)
	l = 0
	cnt = 0
	flag = 1
	(sl, sr) = (1, 1)
	while l < r:
		isSwapped = 1
		flag2 = 1
		if str_list[l] != str_list[r]:
			isSwapped = 0
			if l + 1 == r:
				flag = 0
				break
			if str_list[l + 1] == str_list[r] and sl:
				(str_list[l], str_list[l + 1]) = (str_list[l + 1], str_list[l])
				isSwapped = 1
				flag2 = 0
				sl = 0
				sr = 1
				cnt += 1
			elif str_list[r - 1] == str_list[l] and sr:
				(str_list[r - 1], str_list[r]) = (str_list[r], str_list[r - 1])
				isSwapped = 1
				flag2 = 0
				sr = 0
				sl = 1
				cnt += 1
		if isSwapped == 0:
			flag = 0
			break
		if flag2:
			(sl, sr) = (1, 1)
		l += 1
		r -= 1
	if flag:
		print('YES', cnt, sep='\n')
	else:
		print('NO')
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	s = list(s)
	done = set()
	i = 0
	j = n - 1
	ans = 0
	while i < j:
		if s[i] != s[j]:
			if s[i] == s[j - 1] and (j not in done and j - 1 not in done):
				ans += 1
				(s[j - 1], s[j]) = (s[j], s[j - 1])
				done.add(j)
				done.add(j - 1)
			elif s[j] == s[i + 1] and (i not in done and i + 1 not in done):
				ans += 1
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				done.add(i)
				done.add(i + 1)
		i += 1
		j -= 1
	(i, j) = (0, n - 1)
	check = False
	while i < j:
		if s[i] != s[j]:
			check = True
			print('NO')
			break
		i += 1
		j -= 1
	if not check:
		print('YES')
		print(ans)
	t -= 1


for t in range(int(input())):
	n = int(input())
	s = list(input())
	dp = [0] * n
	count = 0
	f = True
	if len(s) == 2:
		if s[0] != s[1]:
			f = False
	for i in range(n - 1):
		if s[i] == s[n - i - 1]:
			continue
		elif s[i + 1] == s[n - i - 1] and dp[i] == 0 and (dp[i + 1] == 0):
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			dp[i] = dp[i + 1] = 1
			count += 1
		elif s[i] == s[n - i - 2] and dp[n - i - 1] == 0 and (dp[n - i - 2] == 0):
			(s[n - i - 1], s[n - i - 2]) = (s[n - i - 2], s[n - i - 1])
			dp[n - i - 1] = dp[n - i - 2] = 1
			count += 1
		else:
			f = False
			break
	if f:
		print('YES')
		print(count)
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	j = n - 1
	f = 1
	l = [1 for i in range(n)]
	res = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif i == j - 1:
			res = -1
			break
		elif l[j] and l[j - 1] and (s[i] == s[j - 1]):
			(s[j], s[j - 1]) = (s[j - 1], s[j])
			l[j] = 0
			l[j - 1] = 0
			res += 1
		elif l[i] and l[i + 1] and (s[j] == s[i + 1]):
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			l[i] = 0
			l[i + 1] = 0
			res += 1
		else:
			res = -1
			break
	if res == -1:
		print('NO')
	else:
		print('YES')
		print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	length = n
	i = 0
	j = n - 1
	ans = True
	steps = 0
	front = False
	back = False
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			front = False
			back = False
		elif i + 1 < j and s[i + 1] == s[j] and (not front):
			s[i + 1] = s[i]
			steps += 1
			i += 1
			j -= 1
			front = True
			back = False
		elif i < j - 1 and s[i] == s[j - 1] and (not back):
			s[j - 1] = s[j]
			steps += 1
			i += 1
			j -= 1
			front = False
			back = True
		else:
			ans = False
			break
	if ans:
		print('YES')
		print(steps)
	else:
		print('NO')


for _ in range(int(input())):
	(n, ans1, ans) = (int(input()), 0, 0)
	s1 = str(input())
	s = [i for i in s1]
	(i, st, ed) = (0, True, True)
	while i < n // 2:
		if s[i] == s[n - i - 1]:
			st = True
			ed = True
		elif n - i - 2 != i and s[i] == s[n - i - 2] and ed:
			(s[n - 1 - i], s[n - i - 2]) = (s[n - i - 2], s[n - 1 - i])
			ans += 1
			st = True
			ed = False
		elif i + 1 != n - i - 1 and s[i + 1] == s[n - i - 1] and st:
			(s[i + 1], s[i]) = (s[i], s[i + 1])
			ans += 1
			st = False
			ed = True
		i += 1
	if s == s[::-1]:
		print('YES')
		print(ans)
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [x for x in input()]
	temp = 0
	ans = 0
	for i in range(n // 2):
		if arr[i] == arr[n - 1 - i]:
			temp = 0
		elif arr[i + 1] == arr[n - 1 - i] and temp != -1 and (i + 1 != n - 1 - i):
			ans += 1
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			temp = -1
		elif arr[i] == arr[n - 2 - i] and temp != 1 and (i != n - 2 - i):
			ans += 1
			(arr[n - 1 - i], arr[n - 2 - i]) = (arr[n - 2 - i], arr[n - 1 - i])
			temp = 1
		else:
			ans = -1
			break
	if ans == -1:
		print('NO')
	else:
		print('YES')
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(input())
	l1 = [0] * n
	c = 0
	e = 0
	for i in range(n // 2):
		if l[i] != l[n - i - 1]:
			if l[i + 1] == l[n - i - 1] and l1[i] == 0 and (i + 1 != n - i - 1):
				c += 1
				(l[i + 1], l[i]) = (l[i], l[n - i - 1])
				l1[i + 1] = 1
				l1[i] = 1
			elif l[n - i - 2] == l[i] and l1[n - i - 1] == 0 and (i != n - i - 2):
				c += 1
				(l[n - i - 1], l[n - i - 2]) = (l[n - i - 2], l[n - i - 1])
				l1[n - i - 1] = 1
				l1[n - i - 2] = 1
			else:
				e = 1
				print('NO')
				break
	if e == 0:
		print('YES')
		print(c)


for _ in range(0, int(input())):
	n = int(input())
	a = list(input())
	start = 0
	end = n - 1
	ans = 0
	swapped = [0] * n
	flag = False
	while start < end:
		if a[start] == a[end]:
			start += 1
			end -= 1
			continue
		elif start == end - 1:
			if a[start] == a[end]:
				start += 1
				end -= 1
				continue
			else:
				flag = True
				break
		elif swapped[end - 1] == 0 and swapped[end] == 0 and (a[start] == a[end - 1]):
			(a[end], a[end - 1]) = (a[end - 1], a[end])
			swapped[end] = 1
			swapped[end - 1] = 1
			ans += 1
			start += 1
			end -= 1
			continue
		elif swapped[start] == 0 and swapped[start + 1] == 0 and (a[start + 1] == a[end]):
			(a[start], a[start + 1]) = (a[start + 1], a[start])
			swapped[start] = 1
			swapped[start + 1] = 1
			ans += 1
			start += 1
			end -= 1
			continue
		else:
			flag = True
			break
	if flag == True:
		print('NO')
	else:
		print('YES')
		print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = input()
	data = list(arr)
	status = False
	test = [0] * n
	min_operations = 0
	for i in range(n):
		j = n - 1 - i
		if i >= j:
			break
		elif data[i] != data[j]:
			if i + 1 != j and (data[i + 1] == data[j] and (test[i] != 1 and test[i + 1] != 1)):
				(data[i], data[i + 1]) = (data[i + 1], data[i])
				test[i] = 1
				test[i + 1] = 1
				test[j] = 1
				min_operations += 1
			elif j - 1 != i and (data[j - 1] == data[i] and (test[j] != 1 and test[j - 1] != 1)):
				(data[j], data[j - 1]) = (data[j - 1], data[j])
				test[j] = 1
				test[j - 1] = 1
				test[i] = 1
				min_operations += 1
			else:
				status = True
		if status == True:
			break
	if status == False:
		print('YES')
		print(min_operations)
	else:
		print('NO')


def swap(s, i, j):
	temp = s[i]
	s[i] = s[j]
	s[j] = temp
	return s
t = int(input())
for k in range(t):
	n = int(input())
	s = list(str(input()))
	left = 0
	n = len(s)
	right = n - 1
	impossible = 0
	count = 0
	rTurn = False
	lTurn = False
	while True:
		if right - left + 1 == 3:
			if s[right] == s[left]:
				break
			else:
				if s[right] == s[right - 1]:
					if lTurn:
						impossible = 1
						break
					else:
						count = count + 1
						break
				if s[left] == s[left + 1]:
					if rTurn:
						impossible = 1
						break
					else:
						count = count + 1
						break
				impossible = 1
				break
		if right - left + 1 == 2:
			if s[right] == s[left]:
				break
			else:
				impossible = 1
				break
		if right - left + 1 <= 1:
			break
		left1 = s[left]
		left2 = s[left + 1]
		right1 = s[right]
		right2 = s[right - 1]
		if left1 == right1:
			lTurn = False
			rTurn = False
			left = left + 1
			right = right - 1
			continue
		if left1 != right1:
			if left1 == right2 and left2 == right1:
				rTurn = False
				lTurn = False
				count = count + 1
				left = left + 2
				right = right - 2
				continue
			if left1 == right2:
				if rTurn:
					impossible = 1
					break
				s = swap(s, right, right - 1)
				rTurn = True
				lTurn = False
				count = count + 1
				left = left + 1
				right = right - 1
				continue
			if left2 == right1:
				if lTurn:
					impossible = 1
					break
				lTurn = True
				rTurn = False
				s = swap(s, left, left + 1)
				count = count + 1
				left = left + 1
				right = right - 1
				continue
			else:
				impossible = 1
				break
	if impossible == 1:
		print('NO')
	else:
		print('YES')
		print(count)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	swap = 0
	swaps = [True] * n
	while i < n // 2:
		if s[i] != s[n - i - 1]:
			if s[i] == s[n - i - 2] and swaps[n - i - 2] and swaps[n - i - 1] and (i != n - i - 2):
				(s[n - i - 2], s[n - i - 1]) = (s[n - i - 1], s[n - i - 2])
				swaps[n - i - 2] = False
				swaps[n - i - 1] = False
				swaps[i] = False
				swap += 1
			elif s[i + 1] == s[n - i - 1] and swaps[i] and swaps[i + 1] and (i + 1 != n - i - 1):
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				swaps[i] = False
				swaps[i + 1] = False
				swaps[n - i - 1] = False
				swap += 1
			else:
				print('NO')
				break
		else:
			swaps[i] = False
			swaps[n - i - 1] = False
		i += 1
	else:
		print('YES')
		print(swap)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = list(s)
	(l, r, ans) = (0, n - 1, 0)
	(a, z) = (0, 0)
	while l < r:
		if s[l] == s[r]:
			(a, z) = (0, 0)
			l += 1
			r -= 1
			continue
		if l + 1 == r:
			break
		if s[l + 1] == s[r] and a == 0:
			(a, z) = (1, 0)
			(s[l], s[l + 1]) = (s[l + 1], s[l])
			ans += 1
			l += 1
			r -= 1
		elif s[l] == s[r - 1] and z == 0:
			(a, z) = (0, 1)
			(s[r], s[r - 1]) = (s[r - 1], s[r])
			ans += 1
			l += 1
			r -= 1
		else:
			break
	if s == s[::-1]:
		print('YES')
		print(ans)
	else:
		print('NO')


t = int(input())
for w in range(t):
	n = int(input())
	s = input()
	s = list(s)
	right = len(s) - 1
	f = 1
	ans = 0
	left = 0
	swap_done = {}
	while left < len(s) // 2:
		if s[left] == s[right]:
			right -= 0
		elif s[left] == s[right - 1] and left != right - 1 and (right not in swap_done) and (right - 1 not in swap_done):
			swap_done[right] = 1
			swap_done[right - 1] = 1
			(s[right], s[right - 1]) = (s[right - 1], s[right])
			ans += 1
		elif s[left + 1] == s[right] and left + 1 != right and (left + 1 not in swap_done) and (left not in swap_done):
			swap_done[left] = 1
			swap_done[left + 1] = 1
			(s[left], s[left + 1]) = (s[left + 1], s[left])
			ans += 1
		else:
			f = 0
			break
		left += 1
		right -= 1
	if f == 1:
		print('YES')
		print(ans)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	vis = [False] * n
	fl = True
	c = 0
	for j in range(n // 2 + 1):
		if s[j] == s[n - j - 1]:
			continue
		elif s[j] == s[n - j - 2] and vis[n - j - 1] == False and (vis[n - j - 2] == False) and (j != n - j - 2):
			tm = s[n - j - 1]
			s[n - j - 1] = s[n - j - 2]
			s[n - j - 2] = tm
			vis[n - j - 1] = vis[n - j - 2] = True
			c += 1
		elif s[j + 1] == s[n - j - 1] and vis[j + 1] == False and (vis[j] == False) and (j + 1 != n - j - 1):
			tm = s[j + 1]
			s[j + 1] = s[j]
			s[j] = tm
			vis[j + 1] = vis[j] = True
			c += 1
		else:
			fl = False
			break
	if fl == True:
		print('YES')
		print(c)
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	string = input()
	string = list(string)
	br = False
	bl = False
	r = n - 1
	l = 0
	count = 0
	flag = True
	while r >= 0 and l < n:
		if string[l] == string[r]:
			l += 1
			r -= 1
			(br, bl) = (False, False)
			continue
		if l + 1 == r:
			print('NO')
			flag = False
			break
		if bl == False and string[l + 1] == string[r]:
			(string[l], string[l + 1]) = (string[l + 1], string[l])
			bl = True
			br = False
			count += 1
		elif br == False and string[l] == string[r - 1]:
			(string[r], string[r - 1]) = (string[r - 1], string[r])
			br = True
			bl = False
			count += 1
		else:
			print('NO')
			flag = False
			break
		l += 1
		r -= 1
	if flag:
		print('YES')
		print(count)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	v = [0 for i in range(n)]
	f = True
	c = 0
	for j in range(n // 2 + 1):
		if s[j] == s[n - 1 - j]:
			continue
		elif s[j] == s[n - 2 - j] and v[n - 2 - j] == 0 and (v[n - 1 - j] == 0) and (j != n - 2 - j):
			t = s[n - 2 - j]
			s[n - 2 - j] = s[n - 1 - j]
			s[n - 1 - j] = t
			v[n - 1 - j] = v[n - 2 - j] = 1
			c += 1
		elif s[n - j - 1] == s[j + 1] and v[j] == 0 and (v[j + 1] == 0) and (j + 1 != n - 1 - j):
			t = s[j]
			s[j] = s[j + 1]
			s[j + 1] = t
			v[j] = v[j + 1] = 1
			c += 1
		else:
			f = False
	if f == True:
		print('YES')
		print(c)
	else:
		print('NO')


def swap(s, i, j):
	return ''.join((s[:i], s[j], s[i + 1:j], s[i], s[j + 1:]))
for _ in range(int(input())):
	n = int(input())
	strg = list(input())
	visited = [0 for i in range(n)]
	left = 0
	right = n - 1
	count = 0
	while left < right:
		if strg[left] == strg[right]:
			left += 1
			right -= 1
			continue
		elif strg[left] != strg[right]:
			if strg[left] == strg[right - 1] and visited[right] == 0:
				(strg[right], strg[right - 1]) = (strg[right - 1], strg[right])
				count += 1
				visited[right - 1] = 1
				visited[right] = 1
			elif strg[left + 1] == strg[right] and visited[left] == 0:
				(strg[left + 1], strg[left]) = (strg[left], strg[left + 1])
				count += 1
				visited[left + 1] = 1
				visited[left] = 1
			else:
				break
			left += 1
			right -= 1
	if strg == strg[::-1]:
		print('YES')
		print(count)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	(i, j) = (0, n - 1)
	answer = 0
	occured = set()
	result = True
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			continue
		if i + 1 == j:
			result = False
			break
		if s[i] == s[j - 1] and j not in occured and (j - 1 not in occured):
			(s[j], s[j - 1]) = (s[j - 1], s[j])
			answer += 1
			occured.add(j)
			occured.add(j - 1)
			i += 1
			j -= 1
			continue
		if s[i + 1] == s[j] and i not in occured and (i + 1 not in occured):
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			occured.add(i)
			occured.add(i + 1)
			i += 1
			j -= 1
			answer += 1
			continue
		result = False
		break
	if result:
		print('YES')
		print(answer)
		continue
	print('NO')


t = int(input())

def swap(x, y):
	return (y, x)
while t > 0:
	t -= 1
	n = int(input())
	s = list(input())
	a = [0] * n
	ans = 0
	f = 0
	for (i, j) in zip(range(0, n), range(n - 1, -1, -1)):
		if i > j:
			break
		if s[i] == s[j]:
			a[i] = a[j] = 1
			continue
		sw = False
		if i < n - 1 and s[i + 1] == s[j] and (a[i] != 1):
			if j > 0 and s[i] == s[j - 1] and (not a[j - 1]) or (j > 1 and s[i] == s[j - 2] and (not a[j - 2])):
				sw = True
				ans += 1
				(s[i], s[i + 1]) = swap(s[i], s[i + 1])
				a[i] = 1
				a[i + 1] = 1
		if not sw and j > 0 and (s[j - 1] == s[i]) and (not a[j - 1]):
			if i < n and s[j] == s[i + 1] and (not a[i + 1]) or (i < n - 1 and s[j] == s[i + 2] and (not a[i + 2])):
				ans += 1
				sw = True
				(s[j], s[j - 1]) = swap(s[j], s[j - 1])
				a[j] = 1
				a[j - 1] = 1
	for i in range(0, n):
		if s[i] != s[n - i - 1]:
			f = 1
			break
	if f:
		print('NO')
	else:
		print('YES')
		print(ans)


t = int(input())
for t1 in range(0, t):
	n = int(input())
	s = input()
	d = {}
	countodd = 0
	oddval = ''
	check = 1
	c = 0
	change = -1
	s = list(s)
	l = [1 for i in range(n)]
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d.keys():
		if d[i] % 2 == 1:
			countodd += 1
			oddval = i
	if n % 2 == 1:
		if countodd > 1:
			check = -1
	if n % 2 == 0:
		if countodd > 0:
			check = -1
	if check == -1:
		print('NO')
	else:
		ok = 1
		for i in range(0, n // 2 + 1):
			if s[i] == s[n - 1 - i]:
				ok = 1
			elif s[i] == s[n - i - 2] and l[n - i - 2] == 1 and (l[n - i - 1] == 1):
				(s[n - i - 1], s[n - i - 2]) = (s[n - i - 2], s[n - i - 1])
				c = c + 1
				l[n - i - 2] = l[n - i - 1] = 0
			elif s[i + 1] == s[n - i - 1] and l[i] == 1 and (l[i + 1] == 1):
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				c = c + 1
				l[i] = l[i + 1] = 0
			else:
				check = -1
		if check == -1:
			print('NO')
		else:
			print('YES')
			print(c)


INF = float('inf')
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	ans = 0
	(l, r) = (0, n - 1)
	used = [False] * n
	while l < r:
		if s[l] == s[r]:
			pass
		elif l + 1 < r and s[l + 1] == s[r] and (not used[l]):
			(s[l], s[l + 1]) = (s[l + 1], s[l])
			used[l] = used[l + 1] = True
			ans += 1
		elif l < r - 1 and s[l] == s[r - 1] and (not used[r]):
			(s[r], s[r - 1]) = (s[r - 1], s[r])
			used[r] = used[r - 1] = True
			ans += 1
		l += 1
		r -= 1
	if s != s[::-1]:
		print('NO')
	else:
		print('YES')
		print(ans)


t = int(input())
for k in range(t):
	n = int(input())
	s = input()
	s = list(s)
	v = [0] * n
	c = 0
	f = 0
	for i in range(n // 2 + 1):
		if s[i] == s[n - i - 1]:
			continue
		elif s[i + 1] == s[n - i - 1] and v[i] == 0 and (v[i + 1] == 0) and (i + 1 != n - i - 1):
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			v[i] = 1
			v[i + 1] = 1
			c = c + 1
		elif s[n - i - 2] == s[i] and v[n - i - 1] == 0 and (v[n - i - 2] == 0) and (i != n - i - 2):
			(s[n - i - 1], s[n - i - 2]) = (s[n - i - 2], s[n - i - 1])
			v[n - i - 1] = 1
			v[n - i - 2] = 1
			c = c + 1
		else:
			f = 1
			break
	if f == 0:
		print('YES')
		print(c)
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	s = list(input())
	(l, r) = (0, n - 1)
	flag = 1
	ls = [1 for i in range(n)]
	ans = 0
	while l < r:
		if s[l] == s[r]:
			l += 1
			r -= 1
		elif l == r - 1:
			flag = 0
			break
		elif ls[r] and ls[r - 1] and (s[l] == s[r - 1]):
			(s[r], s[r - 1]) = (s[r - 1], s[r])
			ls[r] = 0
			ls[r - 1] = 0
			ans += 1
		elif ls[l] and ls[l + 1] and (s[r] == s[l + 1]):
			(s[l], s[l + 1]) = (s[l + 1], s[l])
			ls[l] = 0
			ls[l + 1] = 0
			ans += 1
		else:
			flag = 0
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')
		print(ans)


def testcase():
	n = int(input())
	string = list(input())
	hn = n // 2
	ans = 0
	used = [False for i in range(n)]
	for i in range(hn + 1):
		ri = n - 1 - i
		if string[i] == string[ri]:
			used[i] = True
			used[ri] = True
			continue
		if i < hn and string[i] == string[ri - 1] and (not used[ri]) and (not used[ri - 1]):
			ans += 1
			temp = string[ri]
			string[ri] = string[ri - 1]
			string[ri - 1] = temp
			used[i] = True
			used[ri] = True
			used[ri - 1] = True
			continue
		if i < hn and string[i + 1] == string[ri] and (not used[i]) and (not used[i + 1]):
			ans += 1
			temp = string[i]
			string[i] = string[i + 1]
			string[i + 1] = temp
			used[i + 1] = True
			used[i] = True
			used[ri] = True
			continue
		print('NO')
		return
	print('YES\n', ans, sep='')
t = int(input())
for t_ in range(t):
	testcase()


t = int(input())
while t > 0:
	steps = 0
	flag = 0
	n = input()
	s = input()
	m = [x for x in s]
	bl = br = False
	l = 0
	r = len(s) - 1
	while l < r:
		if m[l] == m[r]:
			bl = br = False
			l += 1
			r -= 1
			continue
		elif l == r - 1:
			print('NO')
			flag = 1
			break
		elif m[l] == m[r - 1] and br is False:
			br = True
			bl = False
			steps += 1
			(m[r], m[r - 1]) = (m[r - 1], m[r])
			l += 1
			r -= 1
		elif m[r] == m[l + 1] and bl is False:
			bl = True
			br = False
			steps += 1
			(m[l], m[l + 1]) = (m[l + 1], m[l])
			l += 1
			r -= 1
		else:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')
		print(steps)
	t -= 1


t = int(input())
while t >= 1:
	n = int(input())
	s = list(input())
	j = n - 1
	k = 0
	a = [0] * n
	for i in range(0, int(n // 2)):
		if s[i] != s[j]:
			if s[j - 1] == s[i] and a[j] == 0 and (a[j - 1] == 0) and (j - 1 != i):
				(s[j], s[j - 1]) = (s[j - 1], s[j])
				a[j] = a[j - 1] = 1
			elif s[i + 1] == s[j] and a[i] == 0 and (a[i + 1] == 0) and (i + 1 != j):
				(s[i + 1], s[i]) = (s[i], s[i + 1])
				a[i] = a[i + 1] = 1
			else:
				print('NO')
				k = 1
				break
			j = j - 1
		elif s[i] != s[j] and (a[j] == 1 or a[i] == 1):
			k = 1
			print('NO')
			break
		elif s[i] == s[j]:
			j = j - 1
	if k == 0:
		c = 0
		for i in a:
			if i == 1:
				c = c + 1
		print('YES')
		print(int(c // 2))
	t = t - 1


import math as m
for t in range(int(input())):
	n = int(input())
	p = input()
	s = []
	for i in range(n):
		s.append(p[i])
	cnt = 0
	v = []
	flag = 1
	for i in range(n):
		v.append(0)
	for i in range(n // 2 + 1):
		if s[i] == s[n - 1 - i]:
			continue
		elif s[i] == s[n - i - 2] and v[n - i - 1] == 0 and (v[n - i - 2] == 0) and (i != n - i - 2):
			cnt += 1
			a = s[n - 1 - i]
			s[n - 1 - i] = s[n - i - 2]
			s[n - i - 2] = a
			v[n - i - 1] = 1
			v[n - i - 2] = 1
		elif s[i + 1] == s[n - 1 - i] and v[i] == 0 and (v[i + 1] == 0) and (i + 1 != n - i - 1):
			cnt += 1
			a = s[i + 1]
			s[i + 1] = s[i]
			s[i] = a
			v[i] = 1
			v[i + 1] = 1
		else:
			flag = 2
			break
	if flag == 2:
		print('NO')
	else:
		print('YES')
		print(cnt)


I = input

def solve():
	I()
	s = list(I())
	(c, i, f) = (0, -1, 3)
	for i in range(len(s) // 2):
		if s[i] == s[-1 - i]:
			f = 3
		else:
			c += 1
			if f & 1 and s[i] == s[-2 - i]:
				(s[-2 - i], s[-1 - i]) = (s[-1 - i], s[-2 - i])
				f = 2
			elif f & 2 and s[i + 1] == s[-1 - i]:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				f = 1
			else:
				return -1
	return c if s[i + 1] == s[-2 - i] else -1
t = int(I())
for _ in range(t):
	r = solve()
	if r + 1:
		print('YES')
		print(r)
	else:
		print('NO')


I = input

def solve():
	n = int(I())
	s = list(I())
	i = c = 0
	a = b = True
	while 2 * i < n - 2:
		if s[i] == s[-1 - i]:
			a = b = True
			i += 1
		elif a and s[i] == s[-2 - i]:
			(s[-2 - i], s[-1 - i]) = (s[-1 - i], s[-2 - i])
			(a, b) = (False, True)
			i += 1
			c += 1
		elif b and s[i + 1] == s[-1 - i]:
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			(a, b) = (True, False)
			i += 1
			c += 1
		else:
			return -1
	return c if s[i] == s[-1 - i] else -1
t = int(I())
for _ in range(t):
	r = solve()
	if r + 1:
		print('YES')
		print(r)
	else:
		print('NO')


I = input
t = int(I())
for _ in range(t):
	I()
	s = list(I())
	n = len(s)
	i = c = 0
	a = b = True
	while 2 * i < n - 2:
		if s[i] == s[-1 - i]:
			a = b = True
			i += 1
		elif a and s[i] == s[-2 - i]:
			(s[-2 - i], s[-1 - i]) = (s[-1 - i], s[-2 - i])
			(a, b) = (False, True)
			i += 1
			c += 1
		elif b and s[i + 1] == s[-1 - i]:
			(s[i], s[i + 1]) = (s[i + 1], s[i])
			(a, b) = (True, False)
			i += 1
			c += 1
		else:
			print('NO')
			break
	else:
		if s[i] == s[-1 - i]:
			print('YES')
			print(c)
		else:
			print('NO')


def palindrome(X):
	for i in range(n // 2):
		if X[i] != X[-i - 1]:
			return False
	return True

def operations(s):
	cnt = 0
	vis = [0] * n
	for i in range(n // 2):
		if s[i] != s[-i - 1]:
			cnt += 1
			if s[i + 1] == s[-i - 1] and (not vis[i]) and (not vis[i + 1]):
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				vis[i] = vis[i + 1] = True
			elif s[i] == s[-i - 2] and (not vis[-i - 1]) and (not vis[-i - 2]):
				(s[-i - 1], s[-i - 2]) = (s[-i - 2], s[-i - 1])
				vis[-i - 1] = vis[-i - 2] = True
			else:
				return -1
	if not palindrome(s):
		return -1
	return cnt
for _ in range(int(input())):
	n = int(input())
	x = list(input())
	ans = operations(x)
	if ans == -1:
		print('NO')
	else:
		print('YES')
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	st = list(input())
	(p1, p2) = (-1, n)
	i = 0
	l = n - 1 - i
	count = 0
	ans = True
	while i < n // 2:
		l = n - 1 - i
		if st[i] != st[l]:
			if i + 1 == l:
				ans = False
				break
			if i > p1 and st[i + 1] == st[l]:
				(st[i], st[i + 1]) = (st[i + 1], st[i])
				count += 1
				p1 = i + 1
			elif l < p2 and st[l - 1] == st[i]:
				(st[l - 1], st[l]) = (st[l], st[l - 1])
				count += 1
				p2 = l - 1
			else:
				ans = False
				break
		if not ans:
			break
		i += 1
	if ans:
		print('YES')
		print(count)
	else:
		print('NO')


def isPal(s):
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			return False
	return True

def solve(A):
	ans = 0
	A = list(A)
	rotated = [False for _ in A]
	for i in range(0, len(A) // 2):
		if A[i] != A[-i - 1]:
			ans += 1
			if A[i + 1] == A[-i - 1] and (not rotated[i]) and (not rotated[i + 1]):
				(A[i], A[i + 1]) = (A[i + 1], A[i])
				rotated[i] = rotated[i + 1] = True
			elif A[i] == A[-i - 2] and (not rotated[-i - 1]) and (not rotated[-i - 2]):
				(A[-i - 1], A[-i - 2]) = (A[-i - 2], A[-i - 1])
				rotated[-i - 1] = rotated[-i - 2] = True
			else:
				return -1
	if not isPal(A):
		return -1
	return ans
t = int(input())
while t != 0:
	input()
	s = input()
	ans = solve(s)
	if ans == -1:
		print('NO')
	else:
		print('YES')
		print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = input()
	a = list(a)
	boola = [True for i in range(len(a))]
	temp = (n - 1) // 2
	i = 0
	c = 0
	possible = True
	while i < temp:
		if a[i] != a[n - i - 1]:
			if a[i + 1] == a[n - i - 1] and boola[i]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				boola[i] = False
				boola[i + 1] = False
				c += 1
				i += 1
			elif a[n - i - 2] == a[i] and boola[n - i - 1]:
				(a[n - i - 1], a[n - i - 2]) = (a[n - i - 2], a[n - i - 1])
				boola[n - i - 1] = False
				boola[n - i - 2] = False
				c += 1
				i += 1
			else:
				possible = False
				break
		else:
			i += 1
	if n % 2 == 0 and a[n // 2 - 1] != a[n // 2]:
		possible = False
	print('YES' if possible else 'NO')
	if possible:
		print(c)


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


for _ in range(int(input())):
	N = int(input())
	s = input()
	S = [*s]
	i = 0
	j = N - 1
	freeze = -1
	c = 0
	while i <= j:
		if S[i] != S[j]:
			if S[i + 1] == S[j] and freeze != i:
				(S[i], S[i + 1]) = (S[i + 1], S[i])
				freeze = i + 1
				c += 1
			elif S[j - 1] == S[i] and freeze != j:
				(S[j - 1], S[j]) = (S[j], S[j - 1])
				freeze = j - 1
				c += 1
			else:
				break
		i += 1
		j -= 1
	if S == S[::-1]:
		print('YES')
		print(c)
	else:
		print('NO')


t = int(input())
for x_ in range(t):
	n = int(input())
	p = input()
	s = []
	for i in p:
		s.append(i)
	mid = n // 2
	flag = 0
	count = 0
	isLastSwapped = 0
	isFirstSwapped = 0
	for i in range(mid):
		first = i
		last = n - i - 1
		if s[first] == s[last]:
			isLastSwapped = 0
			isFirstSwapped = 0
			continue
		elif s[first] == s[last - 1] and first < last - 1 and (isLastSwapped == 0):
			temmp = s[last]
			s[last] = s[last - 1]
			s[last - 1] = temmp
			isLastSwapped = 1
			isFirstSwapped = 0
			count += 1
		elif s[first + 1] == s[last] and first + 1 < last and (isFirstSwapped == 0):
			temmp = s[first]
			s[first] = s[first + 1]
			s[first + 1] = temmp
			isFirstSwapped = 1
			isLastSwapped = 0
			count += 1
		else:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')
		print(count)


t = int(input())
for x_ in range(t):
	n = int(input().strip())
	p = input()
	s = []
	for i in p:
		s.append(i)
	flag = 0
	count = 0
	f = 0
	first = 0
	last = n - 1
	while first < last:
		if s[first] == s[last]:
			first += 1
			last -= 1
			f = 0
			continue
		if s[first + 1] == s[last] and first + 1 < last and (f != -1):
			(s[first + 1], s[first]) = (s[first], s[first + 1])
			f = -1
			count += 1
			first += 1
			last -= 1
		elif s[first] == s[last - 1] and first < last - 1 and (f != 1):
			(s[last - 1], s[last]) = (s[last], s[last - 1])
			f = 1
			first += 1
			last -= 1
			count += 1
		else:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')
		print(count)


for _ in range(int(input())):
	N = int(input())
	S = input()
	C = list(S)
	F = 1
	T = 0
	I = 0
	D = [1] * N
	if N % 2 == 0:
		while I < N // 2 - 1:
			if C[I] != C[N - I - 1]:
				if C[I + 1] == C[N - I - 1] and D[I] and D[I + 1]:
					(C[I], C[I + 1]) = (C[I + 1], C[I])
					T += 1
					D[I] = 0
					D[I + 1] = 0
				elif C[I] == C[N - I - 2] and D[N - I - 1] and D[N - I - 2]:
					(C[N - I - 1], C[N - I - 2]) = (C[N - I - 2], C[N - I - 1])
					T += 1
					D[N - I - 1] = 0
					D[N - I - 2] = 0
				else:
					print('NO')
					F = 0
					break
			I += 1
		if F == 1:
			if C[N // 2 - 1] != C[N // 2]:
				print('NO')
				F = 0
	else:
		while I < N // 2:
			if C[I] != C[N - I - 1]:
				if C[I + 1] == C[N - I - 1] and D[I] and D[I + 1]:
					(C[I], C[I + 1]) = (C[I + 1], C[I])
					T += 1
					D[I] = 0
					D[I + 1] = 0
				elif C[I] == C[N - I - 2] and D[N - I - 1] and D[N - I - 2]:
					(C[N - I - 1], C[N - I - 2]) = (C[N - I - 2], C[N - I - 1])
					T += 1
					D[N - I - 1] = 0
					D[N - I - 2] = 0
				else:
					print('NO')
					F = 0
					break
			I += 1
	if F == 1:
		print('YES')
		print(T)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	arr = []
	for ele in s:
		arr.append(ele)
	cond = True
	i = 0
	j = n - 1
	count = 0
	l = [-1] * n
	while i < j:
		if arr[i] != arr[j]:
			if l[i] != -1 and l[j] != -1:
				cond = False
				break
			if l[i] != -1:
				if arr[j - 1] == arr[i] and j - 1 != i:
					count += 1
					(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
					l[j] = 0
					l[j - 1] = 0
				else:
					cond = False
					break
			elif l[j] != -1:
				if arr[i + 1] == arr[j] and i + 1 != j:
					count += 1
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
					l[i] = 0
					l[i + 1] = 0
				else:
					cond = False
					break
			elif arr[j - 1] == arr[i] and j - 1 != i:
				count += 1
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
				l[j] = 0
				l[j - 1] = 0
			elif arr[i + 1] == arr[j] and i + 1 != j:
				count += 1
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				l[i] = 0
				l[i + 1] = 0
			else:
				cond = False
				break
		i += 1
		j -= 1
	if cond == True:
		print('YES')
		print(count)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	flag = 0
	count = 0
	look = [True] * n
	if n % 2 == 0:
		for i in range(n // 2 - 1):
			if s[i] != s[-(i + 1)]:
				if s[i + 1] == s[-(i + 1)] and look[i] and look[i + 1]:
					(s[i], s[i + 1]) = (s[i + 1], s[i])
					(look[i], look[i + 1]) = (False, False)
				elif s[i] == s[-(i + 2)] and look[-(i + 2)] and look[-(i + 1)]:
					(s[-(i + 2)], s[-(i + 1)]) = (s[-(i + 1)], s[-(i + 2)])
					(look[-(i + 1)], look[-(i + 2)]) = (False, False)
				else:
					flag = 1
					break
				count += 1
		if flag == 0:
			if s[n // 2 - 1] != s[n // 2]:
				flag = 1
	else:
		for i in range(n // 2):
			if s[i] != s[-(i + 1)]:
				if s[i + 1] == s[-(i + 1)] and look[i] and look[i + 1]:
					(s[i], s[i + 1]) = (s[i + 1], s[i])
					(look[i], look[i + 1]) = (False, False)
				elif s[i] == s[-(i + 2)] and look[-(i + 2)] and look[-(i + 1)]:
					(s[-(i + 2)], s[-(i + 1)]) = (s[-(i + 1)], s[-(i + 2)])
					(look[-(i + 1)], look[-(i + 2)]) = (False, False)
				else:
					flag = 1
					break
				count += 1
	if flag:
		print('NO')
	else:
		print('YES')
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(input().strip())
	if n == 1:
		print('YES')
		print(0)
		continue
	i = 0
	j = n - 1
	cnt = 0
	flag_index = [True] * n
	flag = True
	while i < j:
		if i + 1 == j and l[i] != l[j]:
			flag = False
			break
		if l[i] == l[j]:
			i += 1
			j -= 1
			continue
		if i + 1 < n and l[i + 1] == l[j] and (flag_index[i + 1] == True) and (flag_index[i] == True):
			(l[i], l[i + 1]) = (l[i + 1], l[i])
			flag_index[i + 1] = False
			flag_index[i] = False
			cnt += 1
			i += 1
			j -= 1
			continue
		if j - 1 >= 0 and l[j - 1] == l[i] and (flag_index[j - 1] == True) and (flag_index[j] == True):
			flag_index[j - 1] = False
			flag_index[j] = False
			(l[j], l[j - 1]) = (l[j - 1], l[j])
			cnt += 1
			i += 1
			j -= 1
			continue
		flag = False
		break
	if flag == True:
		print('YES')
		print(cnt)
	else:
		print('NO')


q = int(input())
for _ in range(q):
	n = int(input())
	l = list(input())
	i = 0
	j = n - 1
	ans = 0
	flag = True
	state = 0
	while i < j:
		if l[i] == l[j]:
			i += 1
			j -= 1
			state = 0
		elif l[i + 1] == l[j] and i + 1 < j and (state != -1):
			ans += 1
			t = l[i]
			l[i] = l[i + 1]
			l[i + 1] = t
			i += 1
			j -= 1
			state = -1
		elif l[i] == l[j - 1] and i + 1 < j and (state != 1):
			ans += 1
			t = l[j]
			l[j] = l[j - 1]
			l[j - 1] = t
			i += 1
			j -= 1
			state = 1
		else:
			flag = False
			print('NO')
			break
	if flag:
		print('YES')
		print(ans)


ts = int(input())
while ts > 0:
	n = int(input().strip())
	st = input()
	st = [i for i in st]
	i = 0
	j = n - 1
	swaps = 0
	flag = 0
	ansflag = 1
	while i < j:
		if st[i] == st[j]:
			i += 1
			j -= 1
			flag = 0
			continue
		if st[i + 1] == st[j] and i + 1 < j and (flag != -1):
			(st[i], st[i + 1]) = (st[i + 1], st[i])
			i += 1
			j -= 1
			flag = -1
			swaps += 1
		elif st[j - 1] == st[i] and i < j - 1 and (flag != 1):
			(st[j - 1], st[j]) = (st[j], st[j - 1])
			i += 1
			j -= 1
			flag = 1
			swaps += 1
		else:
			ansflag = 0
			break
	if ansflag == 1:
		print('YES')
		print(swaps)
	else:
		print('NO')
	ts -= 1


t = int(input())
for w in range(t):
	n = int(input())
	s = list(input())
	l = [-1] * n
	ct = 0
	for i in range(n // 2):
		if s[i] == s[n - i - 1]:
			continue
		if i + 1 < n // 2 or (n % 2 == 1 and i + 1 == n // 2):
			if s[n - i - 1] == s[i + 1] and l[i] == -1 and (l[i + 1] == -1):
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				l[i] = 0
				l[i + 1] = 0
				ct += 1
			elif s[i] == s[n - i - 2] and l[n - i - 1] == -1 and (l[n - i - 2] == -1):
				(s[n - i - 1], s[n - i - 2]) = (s[n - i - 2], s[n - i - 1])
				l[n - i - 1] = 0
				l[n - i - 2] = 0
				ct += 1
			else:
				ct = -1
				break
		else:
			ct = -1
			break
	if ct == -1:
		print('NO')
	else:
		print('YES')
		print(ct)


for t in range(int(input())):
	n = int(input())
	s = [i for i in input()]
	(i, j) = (0, len(s) - 1)
	(ls, rs) = (True, True)
	opt = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			(ls, rs) = (True, True)
		else:
			if s[i + 1] == s[j] and ls:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				(ls, rs) = (False, True)
				opt += 1
			elif s[j - 1] == s[i] and rs:
				(s[j], s[j - 1]) = (s[j - 1], s[j])
				(ls, rs) = (True, False)
				opt += 1
			if s[i] != s[j]:
				opt = -1
				break
			i += 1
			j -= 1
	if opt >= 0:
		print('YES')
		print(opt)
	else:
		print('NO')


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	l = len(s)
	a = []
	for j in s:
		a.append(j)
	m = l // 2
	count = 0
	f1 = 0
	f2 = 0
	flag = 0
	if l == 2:
		if a[0] != a[1]:
			flag = 1
	else:
		for k in range(0, m):
			if a[k] != a[l - k - 1]:
				if a[k] == a[l - k - 2] and f1 == 0 and (k != l - k - 2):
					temp = a[l - k - 1]
					a[l - k - 1] = a[l - k - 2]
					a[l - k - 2] = temp
					count += 1
					f1 = 1
					f2 = 0
				elif a[l - k - 1] == a[k + 1] and f2 == 0 and (k + 1 != l - k - 1):
					temp = a[k]
					a[k] = a[k + 1]
					a[k + 1] = temp
					count += 1
					f1 = 0
					f2 = 1
				else:
					flag = 1
					break
			else:
				f1 = 0
				f2 = 0
	if flag == 1:
		print('NO')
	else:
		print('YES')
		print(count)