Grandma Capa has decided to knit a scarf and asked Grandpa Sher to make a pattern for it, a pattern is a string consisting of lowercase English letters. Grandpa Sher wrote a string $s$ of length $n$.

Grandma Capa wants to knit a beautiful scarf, and in her opinion, a beautiful scarf can only be knit from a string that is a palindrome. She wants to change the pattern written by Grandpa Sher, but to avoid offending him, she will choose one lowercase English letter and erase some (at her choice, possibly none or all) occurrences of that letter in string $s$.

She also wants to minimize the number of erased symbols from the pattern. Please help her and find the minimum number of symbols she can erase to make string $s$ a palindrome, or tell her that it's impossible. Notice that she can only erase symbols equal to the one letter she chose.

A string is a palindrome if it is the same from the left to the right and from the right to the left. For example, the strings 'kek', 'abacaba', 'r' and 'papicipap' are palindromes, while the strings 'abb' and 'iq' are not.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The next $2 \cdot t$ lines contain the description of test cases. The description of each test case consists of two lines.

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

The second line of each test case contains the string $s$ consisting of $n$ lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the minimum number of erased symbols required to make the string a palindrome, if it is possible, and $-1$, if it is impossible.


-----Examples-----

Input
5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky
Output
2
-1
0
3
2


-----Note-----

In the first test case, you can choose a letter 'a' and erase its first and last occurrences, you will get a string 'bcaacb', which is a palindrome. You can also choose a letter 'b' and erase all its occurrences, you will get a string 'acaaca', which is a palindrome as well.

In the second test case, it can be shown that it is impossible to choose a letter and erase some of its occurrences to get a palindrome.

In the third test case, you don't have to erase any symbols because the string is already a palindrome.

Difficulty: EASY
Tags: String algorithms

Amortized analysis

Greedy algorithms

Complete search

Data structures
Skill types: Complete search

Data structures

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	ans = 0
	flag = 0
	ans1 = 0
	while i < j:
		if flag == 1:
			break
		elif s[i] != s[j]:
			ans = 1
			ans1 = 10000000000000
			p = s[i]
			q = s[j]
			c1 = 0
			c2 = 0
			x = i + 1
			y = j
			while x < y:
				if s[x] == s[y]:
					x += 1
					y -= 1
				elif s[x] != s[y] and s[x] != p and (s[y] != p):
					c1 = -1
					break
				else:
					ans += 1
					if s[x] == p:
						x += 1
					else:
						y -= 1
			if c1 != -1:
				ans1 = ans
			x = i
			y = j - 1
			ans = 1
			while x < y:
				if s[x] == s[y]:
					x += 1
					y -= 1
				elif s[x] != s[y] and s[x] != q and (s[y] != q):
					c2 = -1
					break
				else:
					ans += 1
					if s[x] == q:
						x += 1
					else:
						y -= 1
			if c1 == -1 and c2 == -1:
				flag = 1
			if c2 != -1:
				ans1 = min(ans1, ans)
			break
		i += 1
		j -= 1
	if flag:
		print(-1)
	else:
		print(ans1)


def isPalindrome(string, low, high):
	while low < high:
		if string[low] != string[high]:
			return False
		low += 1
		high -= 1
	return True

def solve(s, l):
	low = 0
	high = len(s) - 1
	res = 0
	while low < high:
		if l == s[high] and l == s[low]:
			low += 1
			high -= 1
		elif s[high] == l:
			high -= 1
			res += 1
		elif s[low] == l:
			low += 1
			res += 1
		elif s[low] != s[high]:
			return -1
		else:
			low += 1
			high -= 1
		if isPalindrome(s, low, high):
			return res
	return -1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
		continue
	se = set(s)
	ans = 10 ** 10
	for i in se:
		k = solve(s, i)
		if k != -1:
			ans = min(ans, k)
	print(ans if ans != 10 ** 10 else -1)


from sys import stdin, stdout
t = int(stdin.readline().strip())
for _ in range(t):
	n = int(stdin.readline().strip())
	s = stdin.readline().strip()
	ss = []
	ans = 10000000000000000
	for i in range(n):
		if s[i] not in ss:
			ss.append(s[i])
			l = 0
			r = n - 1
			num = 0
			while l < r:
				if s[l] == s[r]:
					l += 1
					r -= 1
					continue
				if s[l] == s[i] or s[r] == s[i]:
					num += 1
					if s[l] == s[i]:
						l += 1
					else:
						r -= 1
				else:
					num = 10000000000000000
					break
			ans = min(ans, num)
	if ans == 10000000000000000:
		stdout.write(str(-1) + '\n')
	else:
		stdout.write(str(ans) + '\n')


for j in range(int(input())):
	out = -1
	n = int(input())
	s = input()
	d = set(s)
	for i in d:
		a = 0
		l = 0
		r = n - 1
		while l < r and a != -1:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == i:
				l += 1
				a += 1
			elif s[r] == i:
				r -= 1
				a += 1
			else:
				a = -1
		if a != -1 and (out == -1 or a < out):
			out = a
	print(out)


def isPalindrome(s):
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			return 0
	return 1

def all(a, z):
	for i in a:
		if a[i] != z:
			return 0
	return 1
for s in [*open(0)][2::2]:
	s = s[0:len(s)]
	s = s.rstrip('\n')
	n = len(s)
	a = {}
	for i in s:
		a[i] = 0
	for i in a:
		l = 0
		r = n - 1
		while l < r:
			if s[l] != s[r] and s[r] == i:
				r -= 1
				a[i] += 1
			elif s[l] != s[r] and s[l] == i:
				l += 1
				a[i] += 1
			elif s[l] == s[r]:
				l += 1
				r -= 1
			else:
				a[i] = -1
				break
	if all(a, -1):
		print(-1)
	else:
		min = 1000000000
		for i in a:
			if a[i] < min and a[i] >= 0:
				min = a[i]
		print(min)


import sys

def count(n, s, ch):
	i = 0
	j = n - 1
	cnt = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] == ch:
			cnt += 1
			i += 1
		elif s[j] == ch:
			cnt += 1
			j -= 1
		else:
			return sys.maxsize
	return cnt

def fun(n, s):
	import sys
	ans = sys.maxsize
	for ch in set(s):
		c = count(n, s, ch)
		ans = min(ans, c)
	return ans if ans != sys.maxsize else -1
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = fun(n, s)
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
inp_vars_int = lambda : map(int, input().split())
inp_list_int = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	_ = int(input())
	s = input().strip()
	n = len(s)
	pos = False
	res = math.inf
	for c in set(s):
		sr = s
		sr = sr.replace(c, '')
		if sr == sr[::-1]:
			cand = 0
			(ip, ir) = (0, n - 1)
			while ip < ir:
				if s[ip] != s[ir]:
					ip += s[ip] == c
					ir -= s[ir] == c
					cand += 1
				else:
					ip += 1
					ir -= 1
			res = min(res, cand)
	if res == math.inf:
		res = -1
	print(res)


q = int(input())
for i in range(0, q):
	n = int(input())
	s = input()
	ans = n + 1
	for j in range(0, 26):
		(l, r) = (0, n - 1)
		cnt = 0
		while l < r:
			if s[l] == s[r]:
				(l, r) = (l + 1, r - 1)
			elif s[l] == chr(97 + j):
				(l, cnt) = (l + 1, cnt + 1)
			elif s[r] == chr(97 + j):
				(r, cnt) = (r - 1, cnt + 1)
			else:
				cnt = n + 1
				break
		ans = min(ans, cnt)
	if ans == n + 1:
		print(-1)
	else:
		print(ans)


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby, accumulate
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	s = rs()
	(i, j) = (0, n - 1)
	while i < j and s[i] == s[j]:
		(i, j) = (i + 1, j - 1)
	if i >= j:
		print(0)
		continue
	(x, y) = (i, j)
	flag = True
	count = 0
	D = set()
	while i < j:
		if s[i] == s[j]:
			(i, j) = (i + 1, j - 1)
			continue
		else:
			count += 1
			if not D:
				D.add(s[i])
				i += 1
				continue
			elif s[i] in D:
				i += 1
				continue
			elif s[j] in D:
				j -= 1
				continue
			else:
				flag = False
				break
		i += 1
		j -= 1
	res = count if flag else -1
	(i, j) = (x, y)
	flag = True
	count = 0
	D = set()
	while i < j:
		if s[i] == s[j]:
			(i, j) = (i + 1, j - 1)
			continue
		else:
			count += 1
			if not D:
				D.add(s[j])
				j -= 1
				continue
			elif s[i] in D:
				i += 1
				continue
			elif s[j] in D:
				j -= 1
				continue
			else:
				flag = False
				break
		i += 1
		j -= 1
	if res == -1 and flag:
		print(count)
	elif res != -1 and (not flag):
		print(res)
	else:
		print(min(res, count))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = input().rstrip()
	(l, r) = (0, n - 1)
	res = []
	while True:
		if l >= r:
			res = 0
			break
		if a[l] != a[r]:
			res += [l, r]
			break
		l += 1
		r -= 1
	if res == 0:
		print(0)
		continue
	(l, r) = (res[0], res[1])
	(b, c) = (a[l], a[r])
	(resb, resc) = (0, 0)
	flag = 0
	ans = []
	while True:
		if l >= r:
			break
		if a[l] != a[r]:
			if a[l] == b:
				resb += 1
				l += 1
				continue
			elif a[r] == b:
				resb += 1
				r -= 1
				continue
			else:
				flag = 1
				break
		l += 1
		r -= 1
	if flag == 0:
		ans.append(resb)
	(l, r) = (res[0], res[1])
	flag = 0
	while True:
		if l >= r:
			break
		if a[l] != a[r]:
			if a[l] == c:
				resc += 1
				l += 1
				continue
			elif a[r] == c:
				resc += 1
				r -= 1
				continue
			else:
				flag = 1
				break
		l += 1
		r -= 1
	if flag == 0:
		ans.append(resc)
	print(min(ans) if len(ans) else -1)


from string import *
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = n
	flag1 = False
	for j in range(ord('a'), ord('z') + 1):
		c = chr(j)
		l = 0
		r = n - 1
		num = 0
		flag2 = True
		while l < r:
			if s[l] != s[r]:
				if s[l] == c:
					num += 1
					l += 1
				elif s[r] == c:
					num += 1
					r -= 1
				else:
					flag2 = False
					break
			else:
				l += 1
				r -= 1
		if flag2:
			flag1 = True
			ans = min(ans, num)
	if not flag1:
		ans = -1
	print(ans)


import string

def read_nums():
	return [int(x) for x in input().split()]

def erase_letter(ch, s, n):
	res = 0
	(i, j) = (0, n - 1)
	while i < j:
		if s[i] != s[j]:
			if s[i] == ch:
				i += 1
				res += 1
			elif s[j] == ch:
				j -= 1
				res += 1
			else:
				return None
		else:
			i += 1
			j -= 1
	return res

def solve():
	(n,) = read_nums()
	s = input()
	candidates = [erase_letter(ch, s, n) for ch in string.ascii_lowercase]
	if all((c is None for c in candidates)):
		print(-1)
		return
	else:
		return print(min([c for c in candidates if c is not None]))

def main():
	(t,) = read_nums()
	for _ in range(t):
		solve()
main()


lsta = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	dic = {}
	for j in lsta:
		dic[j] = 0
	mi = 1000000000.0
	for c in lsta:
		err = 0
		co = 0
		start = 0
		end = n - 1
		while start < end:
			if s[start] == s[end]:
				start += 1
				end -= 1
			elif s[start] == c:
				start += 1
				co += 1
			elif s[end] == c:
				end -= 1
				co += 1
			else:
				err += 1
				break
		if err == 0:
			mi = min(co, mi)
	if mi == 1000000000.0:
		print(-1)
	else:
		print(mi)


t = int(input())
for h in range(t):
	n = int(input())
	s = input()
	s1 = s
	d1 = 0
	mir = n
	D = []
	j = 0
	k = n - 1
	elc = False
	while j <= k:
		if s[j] != s[k]:
			D = [s[j], s[k]]
			elc = True
			break
		j += 1
		k -= 1
	if elc:
		for i in range(2):
			j1 = j
			k1 = k
			s = s1
			r = 0
			while j1 <= k1:
				if s[j1] != s[k1]:
					if s[j1] == D[i]:
						s = s[:j1] + s[j1 + 1:]
					elif s[k1] == D[i]:
						s = s[:k1] + s[k1 + 1:]
					else:
						break
					r += 1
					k1 -= 1
				else:
					j1 += 1
					k1 -= 1
			if s == s[::-1]:
				if r < mir:
					mir = r
			else:
				d1 += 1
		if d1 == 2:
			print(-1)
		else:
			print(mir)
	else:
		print(0)


from functools import lru_cache
from collections import defaultdict as dd

def longestPalindrome(s: str) -> str:
	dp = dd(lambda : -9999999)

	def retdp(k, v: int) -> int:
		dp[k] = v
		return v

	def do_dp(start, end, remove):

		def valid(oth):
			return remove is None or remove == oth
		t = (start, end, remove)
		if t in dp:
			return dp[t]
		if start == end:
			return retdp(t, 1)
		edges_equal = s[start] == s[end]
		if start + 1 == end:
			if edges_equal:
				return retdp(t, 2)
			if any((valid(c) for c in (s[start], s[end]))):
				return retdp(t, 1)
			return retdp(t, -9999999)
		if s[start] == s[end]:
			yield (start + 1, end - 1, remove)
			res = (yield)
			return retdp(t, 2 + res)
		ma = -9999999
		if valid(s[start]):
			yield (start + 1, end, s[start])
			res = (yield)
			ma = max(res, ma)
		if valid(s[end]):
			yield (start, end - 1, s[end])
			res = (yield)
			ma = max(res, ma)
		return ma
	stack = [do_dp(0, len(s) - 1, None)]
	while not isinstance(stack[0], int):
		coret = stack.pop()
		if isinstance(coret, int):
			real_coret = stack.pop()
			next(real_coret)
			try:
				stack.append(real_coret)
				stack.append(do_dp(*real_coret.send(coret)))
			except StopIteration as e:
				stack.pop()
				stack.append(e.value)
		else:
			try:
				to_do = next(coret)
				stack.append(coret)
				stack.append(do_dp(*to_do))
			except StopIteration as e:
				stack.append(e.value)
	return stack[0]
for t in range(int(input())):
	n = int(input())
	s = input().strip()
	length = longestPalindrome(s)
	if length < 1:
		print(-1)
	else:
		print(n - length)


def test(n, a, i):
	delete = 0
	char = a[i]
	b = i
	e = n - 1 - i
	if b > e:
		(b, e) = (e, b)
	while b < e:
		if a[b] == a[e]:
			b += 1
			e -= 1
			continue
		if a[b] == char:
			b += 1
			delete += 1
			continue
		if a[e] == char:
			e -= 1
			delete += 1
			continue
		else:
			delete = -1
			break
	return delete
t = int(input())
for _ in range(t):
	n = int(input())
	a = str(input())
	b = 0
	e = n - 1
	while b < e and a[b] == a[e]:
		b += 1
		e -= 1
	if b >= e:
		print(0)
		continue
	chb = test(n, a, b)
	che = test(n, a, e)
	if chb + che == -2:
		print(-1)
	elif chb == -1:
		print(che)
	elif che == -1:
		print(chb)
	else:
		print(min(chb, che))


from sys import stdin
from collections import defaultdict
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	s = rs()
	ans = float('inf')
	for char in set(s):
		(l, r) = (0, n - 1)
		pans = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == char:
				l += 1
				pans += 1
			elif s[r] == char:
				r -= 1
				pans += 1
			else:
				pans = float('inf')
				break
		ans = min(ans, pans)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)


n = int(input())
for i in range(n):
	len = int(input())
	line = input()
	c = '0'
	i = 0
	j = len - 1
	a = 0
	f = 0
	while i < j:
		if line[i] != line[j]:
			if a > 0:
				if line[i] == c:
					i += 1
				elif line[j] == c:
					j -= 1
				else:
					f = 1
					break
			else:
				c = line[i]
				i += 1
			a += 1
		else:
			i += 1
			j -= 1
	c = '0'
	i = 0
	j = len - 1
	b = a
	a = 0
	while i < j:
		if line[i] != line[j]:
			if a > 0:
				if line[i] == c:
					i += 1
				elif line[j] == c:
					j -= 1
				else:
					f += 2
					break
			else:
				c = line[j]
				j -= 1
			a += 1
		else:
			i += 1
			j -= 1
	if f == 3:
		print(-1)
	elif f == 2:
		print(b)
	elif f == 1:
		print(a)
	else:
		print(min(a, b))


def ispalindrome(s, c):
	l = 0
	r = len(s) - 1
	ans = 0
	while l <= r:
		if l == r:
			ans += 1
			break
		if s[l] == s[r]:
			ans += 2
			l += 1
			r -= 1
		elif s[l] == c:
			l += 1
		elif s[r] == c:
			r -= 1
		else:
			return 'invalid'
	return ans
for i in range(int(input())):
	n = int(input())
	s = input()
	unique = set(s)
	ans = 0
	for j in unique:
		exp = ispalindrome(s, j)
		if exp != 'invalid':
			ans = max(ans, exp)
	if ans != 0:
		print(n - ans)
	else:
		print(-1)


for test in range(int(input())):
	n = int(input())
	s = input()
	dic = 'abcdefghijklmnopqrstuvwxyz'
	ans = 2 ** 69
	for x in dic:
		l = 0
		r = n - 1
		c = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
				continue
			if s[l] == x:
				l += 1
				c += 1
			elif s[r] == x:
				r -= 1
				c += 1
			else:
				c = 2 ** 69
				break
		ans = min(ans, c)
	if ans == 2 ** 69:
		print(-1)
		continue
	print(ans)


import sys
input = sys.stdin.readline

def isPalin(string):
	l = len(string)
	if l % 2 == 0:
		tmp1 = string[:l // 2]
		tmp2 = string[l // 2:]
		tmp2 = tmp2[::-1]
		if tmp1 == tmp2:
			return True
	else:
		tmp1 = string[:l // 2]
		tmp2 = string[l // 2 + 1:]
		tmp2 = tmp2[::-1]
		if tmp1 == tmp2:
			return True
	return False

def cntSame(string, x):
	(s, e) = (0, len(string) - 1)
	cnt = 0
	while s <= e:
		if string[s] == string[e]:
			s += 1
			e -= 1
		elif string[s] == x:
			cnt += 1
			s += 1
		elif string[e] == x:
			cnt += 1
			e -= 1
	return cnt
t = int(input())
for __ in range(t):
	n = int(input())
	string = input().rstrip()
	flag = 1
	cnt = int(1000000000.0)
	for x in 'abcdefghijklmnopqrstuvwxyz':
		s = string.replace(x, '')
		if isPalin(s):
			nnum = cntSame(string, x)
			cnt = min(cnt, nnum)
			flag = 0
	print(-1 if flag else cnt)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
		continue
	abc = list(set(s))
	sus = []
	for i in abc:
		news = s.replace(i, '', 10 ** 5 + 7)
		if news == news[::-1]:
			sus += [i]
	if len(sus) == 0:
		print(-1)
		continue
	mn = 10 ** 7
	for i in sus:
		l = 0
		r = n - 1
		ans = 0
		while l < r:
			if s[l] != s[r]:
				ans += 1
				if s[l] == i:
					r += 1
				elif s[r] == i:
					l -= 1
			l += 1
			r -= 1
		if ans < mn:
			mn = ans
	print(mn)


from string import ascii_lowercase as alp

def f(s, a):
	(l, r, ans) = (0, len(s) - 1, 0)
	while l < r:
		if s[l] == s[r]:
			l += 1
			r -= 1
		elif s[l] == a:
			l += 1
			ans += 1
		elif s[r] == a:
			r -= 1
			ans += 1
		else:
			return float('inf')
	return ans
for _ in range(int(input())):
	ly = int(input())
	y = input()
	a = float('inf')
	for i in alp:
		a = min(f(y, i), a)
	if a == float('inf'):
		print(-1)
	else:
		print(a)


t = int(input())
for test_case in range(t):
	n = int(input())
	s = list(input())
	try:
		while s[0] == s[-1]:
			s.pop(0)
			s.pop()
			n -= 2
	except:
		print(0)
	if s:
		k = 0
		j = n - 1
		ans = [0, 0]
		while k < j:
			if s[k] == s[j]:
				k += 1
				j -= 1
			elif s[k] == s[0]:
				ans[1] += 1
				k += 1
			elif s[j] == s[0]:
				ans[1] += 1
				j -= 1
			else:
				ans.pop()
				break
		k = 0
		j = n - 1
		while k < j:
			if s[k] == s[j]:
				k += 1
				j -= 1
			elif s[k] == s[-1]:
				ans[0] += 1
				k += 1
			elif s[j] == s[-1]:
				ans[0] += 1
				j -= 1
			else:
				ans.pop(0)
				break
		if not ans:
			print(-1)
		else:
			print(min(ans))


import sys
input = sys.stdin.readline
T = int(input())

def calc(lt, rt, ap):
	global cnt
	while lt < rt:
		if s[lt] == s[rt]:
			lt += 1
			rt -= 1
			continue
		if s[lt] == ap:
			lt += 1
			cnt += 1
		elif s[rt] == ap:
			rt -= 1
			cnt += 1
		else:
			return False
	return True
while T:
	T -= 1
	n = int(input())
	s = list(input())
	ans = 2147000000
	if calc(0, n - 1, s):
		print(0)
		continue
	for i in range(26):
		ap = chr(97 + i)
		cnt = 0
		if calc(0, n - 1, ap):
			ans = min(ans, cnt)
	print(ans if ans != 2147000000 else -1)


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	s = list(s)
	checked = ''
	eras_table = [10000000000000]
	erase = 0
	for i in range(n):
		c = s[i]
		if c in checked:
			continue
		checked = checked + c
		index_1 = 0
		index_2 = n - 1
		erase = 0
		check = True
		while index_1 < index_2:
			if s[index_1] == s[index_2]:
				index_1 += 1
				index_2 -= 1
			elif s[index_1] == c:
				index_1 += 1
				erase += 1
			elif s[index_2] == c:
				index_2 -= 1
				erase += 1
			else:
				check = False
				break
		if check:
			eras_table.append(erase)
	if len(eras_table) == 1:
		print(-1)
	else:
		print(min(eras_table))


def solve(s):
	if s == s[::-1]:
		return 0
	answer = -1
	for c in 'abcdefghijklmnopqrstuvwxyz':
		if c not in s:
			continue
		ss = s.replace(c, '')
		if ss != ss[::-1]:
			continue
		candidate = 0
		(start, end) = (0, len(s) - 1)
		while start < end:
			if s[start] == s[end]:
				start += 1
				end -= 1
				continue
			candidate += 1
			if s[start] == c:
				start += 1
				continue
			if s[end] == c:
				end -= 1
				continue
		if answer >= 0:
			answer = min(answer, candidate)
		else:
			answer = candidate
	return answer
t = int(input())
for _ in range(t):
	n = input()
	s = input()
	print(solve(s))


T = int(input())
for _ in range(T):
	N = int(input())
	S1 = list(input())
	S2 = S1[::-1]
	flag = True
	bug = []
	for i in range(N):
		if S1[i] == S2[i]:
			continue
		else:
			bug.append(S1[i])
			bug.append(S2[i])
			flag = False
			break
	if flag:
		print(0)
		continue
	cand = []
	for c in bug:
		T = []
		for s in S1:
			if s == c:
				continue
			T.append(s)
		if T == T[::-1]:
			cand.append(c)
	if not cand:
		print(-1)
		continue
	ans = 1 << 60
	for c in cand:
		C1 = []
		C2 = []
		tmp = 0
		for s in S1:
			if s == c:
				tmp += 1
			else:
				C1.append(tmp)
				tmp = 0
		C1.append(tmp)
		C2 = C1[::-1]
		tmp_ans = 0
		for i in range(len(C1)):
			tmp_ans += abs(C1[i] - C2[i])
		ans = min(ans, tmp_ans)
	print(ans // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	s = set(a)
	s.add('#')
	m = -1
	for ch in s:
		b = a.replace(ch, '')
		if b != b[::-1]:
			continue
		l = 0
		r = n - 1
		cnt = 0
		while l < r:
			if a[l] != a[r] and a[l] == ch:
				l += 1
				cnt += 1
			elif a[l] != a[r] and a[r] == ch:
				r -= 1
				cnt += 1
			elif a[l] != a[r]:
				cnt = -1
				break
			else:
				l += 1
				r -= 1
		if m == -1:
			m = cnt
		else:
			m = min(m, cnt)
	print(m)


def pal(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(s, i, j, n):
	tem = None
	count = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			if i < n - 1 and s[i + 1] == s[j]:
				if not tem or tem == s[i]:
					count += 1
					if not tem:
						tem = s[i]
					i += 2
					j -= 1
					continue
			if j - 1 >= 0 and s[j - 1] == s[i]:
				if not tem or (tem and tem == s[j]):
					count += 1
					if not tem:
						tem = s[j]
					j -= 2
					i += 1
					continue
			return -1
	return count
for t in range(int(input())):
	n = int(input())
	s = input()
	if pal(s):
		print(0)
		continue
	ans = float('inf')
	for i in range(ord('a'), ord('z') + 1):
		ch = chr(i)
		if ch in s:
			i = 0
			j = len(s) - 1
			count = 0
			while i < j:
				if s[i] == s[j]:
					i += 1
					j -= 1
				elif s[i] == ch:
					count += 1
					i += 1
				elif s[j] == ch:
					count += 1
					j -= 1
				else:
					count = float('inf')
					break
			ans = min(ans, count)
	if ans != float('inf'):
		print(ans)
	else:
		print(-1)


import os
import sys
from math import *
from bisect import *
from io import BytesIO, IOBase
from typing import overload

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = int(1000000000.0 + 7)
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
from string import ascii_lowercase
for _ in range(Int()):
	n = Int()
	s = input()
	ans = inf
	for ch in ascii_lowercase:
		ok = True
		rem = 0
		l = 0
		r = n - 1
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == ch:
				l += 1
				rem += 1
			elif s[r] == ch:
				r -= 1
				rem += 1
			else:
				ok = False
				break
		if ok:
			ans = min(ans, rem)
	if ans == inf:
		ans = -1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = float('inf')
	for i in range(26):
		(l, r, temp) = (0, n - 1, 0)
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == chr(97 + i):
				l += 1
				temp += 1
			elif s[r] == chr(97 + i):
				r -= 1
				temp += 1
			else:
				temp = float('inf')
				break
		res = min(res, temp)
	print([res, -1][res == float('inf')])


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

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

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve(n, s):
	start = 0
	end = n - 1
	while start < end:
		if s[start] == s[end]:
			start += 1
			end -= 1
		else:
			break
	if start > end:
		print(0)
		return
	s = s[start:end + 1]
	n = len(s)
	if n == 1:
		print(0)
		return
	ans = float('inf')
	current = 1
	temp = s[0]
	start = 1
	end = n - 1
	flag = 0
	while start <= end and flag == 0:
		if s[start] == s[end]:
			start += 1
			end -= 1
		elif s[start] == temp:
			current += 1
			start += 1
		elif s[end] == temp:
			current += 1
			end -= 1
		else:
			flag = 1
			break
	if flag == 0:
		ans = min(ans, current)
	current = 1
	temp = s[-1]
	start = 0
	end = n - 2
	flag = 0
	while start <= end and flag == 0:
		if s[start] == s[end]:
			start += 1
			end -= 1
		elif s[start] == temp:
			current += 1
			start += 1
		elif s[end] == temp:
			current += 1
			end -= 1
		else:
			flag = 1
			break
	if flag == 0:
		ans = min(ans, current)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)
T = get_int()
while T:
	n = get_int()
	s = get_string()
	solve(n, s)
	T -= 1


def f(s, l):
	num = 0
	(a, b) = (0, len(s) - 1)
	while a < b:
		if s[a] == s[b]:
			a += 1
			b -= 1
		elif s[a] == l:
			a += 1
			num += 1
		elif s[b] == l:
			b -= 1
			num += 1
		else:
			return len(s)
	return num
case = int(input())
for i in range(case):
	n = int(input())
	s = input()
	m = n
	for j in range(97, 123):
		m = min(m, f(s, chr(j)))
	if m == n:
		print(-1)
	else:
		print(m)


def is_palindrome(s):
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			break
	else:
		return True
	return False
for i in range(int(input())):
	n = int(input())
	s = input()
	alphabet = list(set(s))
	flag = False
	maximum = -1
	for symbol in alphabet:
		if is_palindrome(s.replace(symbol, '')):
			flag = True
			(index, length) = (0, n)
			lst = list(s)
			while index < length // 2:
				if lst[index] != symbol != lst[-index - 1]:
					index += 1
				elif lst[index] == symbol == lst[-index - 1]:
					index += 1
				elif lst[index] == symbol:
					lst.pop(index)
					length -= 1
				else:
					lst.pop(-index - 1)
					length -= 1
			maximum = max(maximum, length)
	if flag:
		print(n - maximum)
	else:
		print(-1)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	n = I()
	s = S()
	m = math.inf
	for i in range(97, 123):
		ch = chr(i)
		c = f = 0
		l = 0
		r = n - 1
		if s.find(ch) == -1:
			continue
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == ch:
				l += 1
				c += 1
			elif s[r] == ch:
				r -= 1
				c += 1
			else:
				f = 1
				break
		if f == 0:
			m = min(c, m)
	if m == math.inf:
		print(-1)
	else:
		print(m)


import sys
from collections import Counter

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
sys.setrecursionlimit(20000)
T = int(input())
for _ in range(T):
	n = get_ints()[0]
	s = sys.stdin.readline()
	count = Counter()
	for ss in s:
		count[ss] += 1
	ans = -1
	for x in count:
		l = 0
		r = n - 1
		removals = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == x:
				l += 1
				removals += 1
			elif s[r] == x:
				r -= 1
				removals += 1
			else:
				removals = -1
				break
		if removals != -1:
			if removals <= ans or ans == -1:
				ans = removals
	print(ans)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def inps():
	return input().strip()

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	s = insr()
	mn = sys.maxsize
	st = set(s)
	flag = 0
	for each in st:
		(strt, end) = (0, n - 1)
		cnt = 0
		tf = 1
		while strt < end:
			if s[strt] == each:
				if s[end] == each:
					strt += 1
					end -= 1
				else:
					strt += 1
					cnt += 1
			elif s[end] == each:
				end -= 1
				cnt += 1
			elif s[strt] == s[end]:
				strt += 1
				end -= 1
			else:
				tf = 0
				break
		if tf:
			mn = min(mn, cnt)
	if mn == sys.maxsize:
		mn = -1
	print(mn)


def compute(s, c):
	i = 0
	j = len(s) - 1
	count = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
			continue
		if s[i] == c:
			i += 1
			count += 1
			continue
		if s[j] == c:
			j -= 1
			count += 1
			continue
		return -1
	return count
t = int(input())
for _ in range(t):
	n = input()
	s = input()
	i = 0
	j = len(s) - 1
	while i < j and s[i] == s[j]:
		i += 1
		j -= 1
	if i >= j:
		print(0)
		continue
	t1 = compute(s[i:j + 1], s[i])
	t2 = compute(s[i:j + 1], s[j])
	if t1 == -1 and t2 == -1:
		print(-1)
	elif t1 == -1:
		print(t2)
	elif t2 == -1:
		print(t1)
	else:
		print(min(t1, t2))


def solve(s):
	l = 0
	r = len(s) - 1
	lock = None
	c = 0
	while l < r:
		if s[l] != s[r]:
			if lock == None or lock == s[l]:
				c += 1
				lock = s[l]
				l += 1
			elif lock == s[r]:
				c += 1
				r -= 1
			else:
				return -1
		else:
			l += 1
			r -= 1
	return c

def solveR(s):
	l = 0
	r = len(s) - 1
	lock = None
	c = 0
	while l < r:
		if s[l] != s[r]:
			if lock == None or lock == s[r]:
				lock = s[r]
				c += 1
				r -= 1
			elif lock == s[l]:
				c += 1
				l += 1
			else:
				return -1
		else:
			l += 1
			r -= 1
	return c
for _ in range(int(input())):
	input()
	s = input()
	sl = solve(s)
	sr = solveR(s)
	if sl == -1 or sr == -1:
		print(max(sl, sr))
	else:
		print(min(sl, sr))


def removechar(s, l):
	n = len(s)
	front = 0
	rear = n - 1
	rm = 0
	while front < rear:
		if s[front] == l and s[rear] != l:
			rm += 1
			front += 1
		elif s[front] != l and s[rear] == l:
			rm += 1
			rear -= 1
		elif s[front] == s[rear]:
			front += 1
			rear -= 1
	return rm

def palin(s):
	n = len(s)
	front = 0
	rear = n - 1
	while front < rear:
		if s[front] == s[rear]:
			front += 1
			rear -= 1
		else:
			return False
	return True

def f(s):
	letters = set()
	for i in s:
		letters.add(i)
	minrm = -1
	for l in letters:
		ns = s.replace(l, '')
		if palin(ns):
			rm = removechar(s, l)
			if rm < minrm or minrm == -1:
				minrm = rm
	return minrm
tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	ans = f(s)
	print(ans)


from string import ascii_lowercase as al
for _ in range(int(input())):
	n = int(input())
	s = input()
	answers = []
	for i in al:
		if i in s:
			(l, r) = (0, n - 1)
			res = 0
			ans = 1000000000.0
			while l < r and r > -1 and (l < n):
				if s[r] == s[l]:
					r -= 1
					l += 1
				elif s[l] == i:
					l += 1
					res += 1
				elif s[r] == i:
					r -= 1
					res += 1
				else:
					ans = -1
					break
			ans = min(ans, res)
			if ans != -1:
				answers.append(ans)
	if answers:
		print(min(answers))
	else:
		print(-1)


import sys
input = sys.stdin.readline

def pallindrome_check(ex):
	i = 0
	j = n - 1
	cnt = 0
	while i < j:
		while string[i] != string[j]:
			if string[i] == ex:
				i += 1
				cnt += 1
			elif string[j] == ex:
				j -= 1
				cnt += 1
			else:
				return -1
		i += 1
		j -= 1
	return cnt

def knit():
	global string, n
	n = int(input())
	string = input()
	if pallindrome_check('') != -1:
		return 0
	min_change = n
	for i in range(26):
		value = pallindrome_check(chr(i + 97))
		if value == -1:
			continue
		min_change = min(min_change, value)
	if min_change == n:
		return -1
	return min_change
string = ''
n = 0
for _ in range(int(input())):
	print(knit())


def f(a):
	anses = []
	for x in range(26):
		ans = 0
		(l, r) = (0, len(a) - 1)
		while r > l:
			if s[l] != s[r]:
				if s[l] == x:
					l += 1
					ans += 1
				elif s[r] == x:
					r -= 1
					ans += 1
				else:
					ans = -1
					break
			else:
				l += 1
				r -= 1
		if ans != -1:
			anses.append(ans)
	return -1 if len(anses) == 0 else min(anses)
t = int(input())
for i in range(t):
	n = int(input())
	s = [ord(x) - ord('a') for x in input()]
	print(f(s))


def solve(s):
	ls = len(s)
	ans = 2 << 64
	for ch in 'abcdefghijklmnopqrstuvwxyz':
		i = 0
		j = ls - 1
		curAns = 0
		while j - i + 1 > 3 and i < ls and (j >= 0):
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == ch:
				i += 1
				curAns += 1
			elif s[j] == ch:
				j -= 1
				curAns += 1
			else:
				curAns += 2
				i += 1
				j -= 1
		if i < ls and j >= 0:
			if j - i + 1 == 1:
				curAns += 1
			elif j - i + 1 == 2:
				curAns += 0 if s[i] == s[j] else 1
			elif j - i + 1 == 3:
				curAns += 0 if s[i] == s[j] else 1
				curAns += 0 if s[i] == s[j - 1] or s[i + 1] == s[j] else 1
		ans = min(curAns, ans)
	return ans

def solve2(s):
	ls = len(s)
	ans = float('inf')
	for ch in 'abcdefghijklmnopqrstuvwxyz':
		i = 0
		j = ls - 1
		curAns = 0
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == ch:
				i += 1
				curAns += 1
			elif s[j] == ch:
				j -= 1
				curAns += 1
			else:
				curAns = float('inf')
				break
		ans = min(ans, curAns)
	if ans == float('inf'):
		return -1
	else:
		return ans
for _ in range(int(input())):
	_ = input()
	s = input().strip()
	print(solve2(s))


from math import *
import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	s = st()
	fl = 0
	rem = 10 ** 6
	for i1 in range(26):
		z = s.count(chr(97 + i1))
		pl = 0
		(i, j) = (0, n - 1)
		while i <= j:
			if i == j:
				if s[i] == chr(97 + i1):
					z -= 1
					break
			if s[i] == s[j]:
				if s[i] == chr(97 + i1):
					z -= 2
					i += 1
					j -= 1
				else:
					i += 1
					j -= 1
			elif s[i] == chr(97 + i1):
				i += 1
			elif s[j] == chr(97 + i1):
				j -= 1
			else:
				pl = 1
				break
		if pl == 0:
			fl = 1
			rem = min(rem, z)
	if fl == 0:
		rem = -1
	print(rem)


from sys import stdin
from typing import Deque
read = stdin.readline
for _ in range(int(read())):
	n = int(read())
	s = Deque(read())
	s.pop()
	i = 0
	j = n - 1
	while i < j:
		if s[i] != s[j]:
			break
		else:
			i += 1
			j -= 1
	if i > j or i == j:
		print(0)
		continue
	l = i
	r = j
	ans1 = 0
	main = s[i]
	while i < j:
		if s[i] != s[j] and s[i] == main:
			i += 1
			ans1 += 1
		elif s[i] != s[j] and s[j] == main:
			j -= 1
			ans1 += 1
		elif s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] != s[j] and s[i] != main:
			ans1 = 10 ** 30
			break
	i = l
	j = r
	ans2 = 0
	main = s[j]
	while i < j:
		if s[i] != s[j] and s[i] == main:
			i += 1
			ans2 += 1
		elif s[i] != s[j] and s[j] == main:
			j -= 1
			ans2 += 1
		elif s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] != s[j] and s[i] != main:
			ans2 = 10 ** 30
			break
	print(-1) if min(ans1, ans2) == 10 ** 30 else print(min(ans1, ans2))


def palindrome(word, string):
	m = len(string)
	j = m - 1
	i = 0
	count = 0
	while i < j:
		if string[i] == string[j]:
			i += 1
			j -= 1
		elif string[i] == word:
			i += 1
			count += 1
		elif string[j] == word:
			j -= 1
			count += 1
		else:
			return -1
	return count
t = int(input())
for case in range(t):
	n = int(input())
	a = input()
	ans = float('inf')
	for i in range(26):
		res = palindrome(chr(97 + i), a)
		if res != -1:
			ans = min(ans, res)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
from itertools import permutations
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_c():
	n = get_int()
	s = list(get_str())
	alpha = string.ascii_lowercase
	best = float('inf')
	for char in alpha:
		l = 0
		r = n - 1
		cnt = 0
		good = True
		while r > l:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == char:
				l += 1
				cnt += 1
			elif s[r] == char:
				r -= 1
				cnt += 1
			else:
				good = False
				break
		if good:
			best = min(best, cnt)
	if best == float('inf'):
		best = -1
	return best
t = get_int()
for _ in range(t):
	print(solve_c())


import sys
input = sys.stdin.readline

def get_integers():
	return map(int, input().strip().split())
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip()
	char_set = set(s)
	min_cnt = n
	for char in char_set:
		(l, r) = (0, n - 1)
		cnt = 0
		flag = True
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
				continue
			if s[l] == char:
				l += 1
			elif s[r] == char:
				r -= 1
			else:
				flag = False
				break
			cnt += 1
		if flag:
			min_cnt = min(cnt, min_cnt)
	print(min_cnt if min_cnt != n else -1)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = n
	for k in range(97, 123):
		c = chr(k)
		(i, j) = (0, n - 1)
		ch = 1
		r = 0
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == c:
				r += 1
				i += 1
			elif s[j] == c:
				r += 1
				j -= 1
			else:
				ch = 0
				break
		if ch:
			ans = min(ans, r)
	if ans == n:
		ans = -1
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
	else:
		ans = 1000000000.0
		for k in 'abcdefghijklmnopqrstuvwxyz':
			a = 0
			b = n - 1
			e = 0
			ch = 0
			while a <= b:
				if s[a] == s[b]:
					a += 1
					b -= 1
				elif s[a] == k:
					a += 1
					ch += 1
				elif s[b] == k:
					b -= 1
					ch += 1
				else:
					ch = 1000000000.0
					break
			ans = min(ans, ch)
		if ans == 1000000000.0:
			print(-1)
		else:
			print(ans)


import sys
for _ in range(int(input())):
	n = int(input())
	s = input()
	(start, end) = (0, len(s) - 1)
	while start < end and s[start] == s[end]:
		start += 1
		end -= 1
	if start >= end:
		print(0)
		continue
	r = 1000000
	for l in [s[start], s[end]]:
		(s1, e1, m) = (start, end, 0)
		while s1 < e1:
			if s[s1] == s[e1]:
				s1 += 1
				e1 -= 1
				continue
			if s[s1] == l:
				s1 += 1
				m += 1
				continue
			if s[e1] == l:
				e1 -= 1
				m += 1
				continue
			break
		if s1 >= e1:
			r = min(r, m)
	print(-1 if r == 1000000 else r)


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def go(s, x):
	a = ''
	n = len(s)
	for i in s:
		if i != x:
			a += i
	if a != a[::-1]:
		return inf
	i = 0
	j = n - 1
	c = 0
	while i <= j:
		d = s[i]
		b = s[j]
		if d == b:
			c += 1
			c += 1 if i != j else 0
			i += 1
			j -= 1
		elif d == x:
			i += 1
		else:
			j -= 1
	return n - c

def solve():
	n = ii()
	s = input()
	ans = inf
	for i in set(s):
		ans = min(go(s, i), ans)
	print(ans if ans != inf else -1)
for _ in ' ' * ii():
	solve()


t = int(input())
import math
for _ in range(t):
	n = int(input())
	s = input()

	def valid(i, j, sy):
		count = 1
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				if s[i] != sy and s[j] != sy:
					return math.inf
				if s[i] == sy:
					i += 1
				else:
					j -= 1
				count += 1
		return count
	i = 0
	j = len(s) - 1
	while i < j and s[i] == s[j]:
		i += 1
		j -= 1
	if i == j or i > j:
		val = 0
	else:
		val = min(valid(i + 1, j, s[i]), valid(i, j - 1, s[j]))
	if val == math.inf:
		print(-1)
	else:
		print(val)


import math
t = int(input())
while t:
	n = int(input())
	s = input()
	ans = n + 1
	for k in range(26):
		l = 0
		r = n - 1
		c = 0
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == chr(ord('a') + k):
				c += 1
				l += 1
			elif s[r] == chr(ord('a') + k):
				r -= 1
				c += 1
			else:
				c = n + 1
				break
		ans = min(ans, c)
	if ans == n + 1:
		ans = -1
	print(ans)
	t -= 1


def test(i, j, l):
	count = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] == l:
			count += 1
			i += 1
		elif s[j] == l:
			count += 1
			j -= 1
		else:
			return n + 2
	return count
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	s = list(input())
	i = 0
	j = n - 1
	problem = False
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			problem = True
			c1 = test(i, j, s[i])
			c2 = test(i, j, s[j])
			best = min(c1, c2)
			i = j + 1
	if not problem:
		print(0)
	elif best < n + 2:
		print(best)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [i for i in s]
	if s == s[::-1]:
		print(0)
		continue
	pt = list(set(l))
	ans = n + 1
	for k in range(len(pt)):
		(i, j, tp, f) = (0, n - 1, 0, 0)
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == pt[k]:
				tp += 1
				i += 1
			elif s[j] == pt[k]:
				tp += 1
				j -= 1
			else:
				f = 1
				break
		if f == 0:
			ans = min(ans, tp)
	if ans == n + 1:
		print(-1)
	else:
		print(ans)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for t in range(int(input())):
	n = int(input())
	s = input()
	value = 0
	s = list(s)
	(i, j) = (0, n - 1)
	pos = 1
	while pos == 1 and i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			a = s[i]
			b = s[j]
			(c1, c2) = (0, 0)
			(ic, jc) = (i, j)
			(pos1, pos2) = (1, 1)
			while ic <= jc:
				if s[ic] == s[jc]:
					ic += 1
					jc -= 1
				elif s[ic] == a:
					c1 += 1
					ic += 1
				elif s[jc] == a:
					c1 += 1
					jc -= 1
				else:
					pos1 = 0
					break
			(ic, jc) = (i, j)
			while ic <= jc:
				if s[ic] == s[jc]:
					ic += 1
					jc -= 1
				elif s[ic] == b:
					c2 += 1
					ic += 1
				elif s[jc] == b:
					c2 += 1
					jc -= 1
				else:
					pos2 = 0
					break
			if pos1 == 1 and pos2 == 1:
				value = min(c1, c2)
			elif pos1 == 1:
				value = c1
			elif pos2 == 1:
				value = c2
			else:
				pos = 0
			break
	if pos == 0:
		print(-1)
	else:
		print(value)


import string

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

def solve_case():
	n = int(input())
	s = input()
	min_r = n + 1
	for ch_i in range(26):
		ch = chr(ord('a') + ch_i)
		i = 0
		j = n - 1
		count = 0
		bad = False
		while i < j:
			if s[i] != s[j]:
				if s[i] == ch:
					i += 1
					count += 1
				elif s[j] == ch:
					j -= 1
					count += 1
				else:
					bad = True
					break
			else:
				i += 1
				j -= 1
		if not bad:
			min_r = min(min_r, count)
	if min_r == n + 1:
		print(-1)
	else:
		print(min_r)
T = int(input())
for t in range(T):
	solve_case()


def case():
	n = int(input())
	s = input()
	l = 0
	r = n - 1
	while l < r:
		x = s[l]
		y = s[r]
		if x == y:
			l += 1
			r -= 1
			continue
		else:
			break
	if l >= r:
		print(0)
		return
	(base_l, base_r) = (l, r)
	c = s[base_l]
	left_ans = 0
	while l < r:
		x = s[l]
		y = s[r]
		if x == y:
			l += 1
			r -= 1
		elif x == c:
			left_ans += 1
			l += 1
		elif y == c:
			left_ans += 1
			r -= 1
		else:
			left_ans = -1
			break
	c = s[base_r]
	(l, r) = (base_l, base_r)
	right_ans = 0
	while l < r:
		x = s[l]
		y = s[r]
		if x == y:
			l += 1
			r -= 1
		elif x == c:
			right_ans += 1
			l += 1
		elif y == c:
			right_ans += 1
			r -= 1
		else:
			right_ans = -1
			break
	if left_ans == -1 and right_ans == -1:
		print(-1)
	elif left_ans == -1:
		print(right_ans)
	elif right_ans == -1:
		print(left_ans)
	else:
		print(min(left_ans, right_ans))

def main():
	T = int(input())
	for _ in range(T):
		case()
main()


def readline():
	return map(int, input().split())

def solve():
	(n,) = readline()
	s = input()
	(i, j) = (0, len(s) - 1)
	while i < j:
		if s[i] != s[j]:
			break
		i += 1
		j -= 1
	if i >= j:
		print(0)
		return
	inf = len(s)

	def check(c):
		ret = 0
		(ii, jj) = (i, j)
		while ii < jj:
			if s[ii] != s[jj]:
				if c == s[ii]:
					ii += 1
				elif c == s[jj]:
					jj -= 1
				else:
					return inf
				ret += 1
			else:
				ii += 1
				jj -= 1
		return ret
	ans = min(map(check, (s[i], s[j])))
	print(ans if ans != inf else -1)
t = int(input())
for __ in range(t):
	solve()


import io, os
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, namedtuple
from math import gcd, ceil, floor, factorial
from itertools import combinations, permutations
input = sys.stdin.readline

def work(n, s):
	if s == s[::-1]:
		return 0
	ans = float('inf')
	seen = set(s)
	for ch in seen:
		flag = True
		(l, r) = (0, n - 1)
		cnt = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == ch:
				l += 1
				cnt += 1
			elif s[r] == ch:
				r -= 1
				cnt += 1
			else:
				flag = False
				break
		if flag:
			ans = min(ans, cnt)
	if ans == float('inf'):
		return -1
	else:
		return ans

def main():
	test = int(input())
	for idt in range(test):
		n = int(input())
		s = input().strip('\r\n')
		ans = work(n, s)
		print(ans)
	return
main()


from string import ascii_lowercase
tc = int(input())
for t in range(tc):
	n = int(input())
	s = input()
	ans = -1
	for c in ascii_lowercase:
		i = 0
		j = n - 1
		flag = cn = 0
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] != c and s[j] != c:
				flag = 1
				break
			elif s[i] == c:
				i += 1
				cn += 1
			else:
				j -= 1
				cn += 1
		if not flag:
			if ans == -1:
				ans = cn
			else:
				ans = min(ans, cn)
	print(ans)


from collections import Counter
import math
import bisect
from sys import stdin, stdout
input = stdin.readline
mod = 10 ** 9 + 7

def inp():
	return map(int, input().split())
res = [chr(i) for i in range(97, 123)]
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = n
	for rs in res:
		i = 0
		j = n - 1
		cur = 0
		c = 1
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == rs:
				i += 1
				cur += 1
			elif s[j] == rs:
				j -= 1
				cur += 1
			else:
				c = 0
				break
		if c:
			ans = min(ans, cur)
	print(ans if ans < n else -1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
inf = float('inf')

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
get = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(get())):
	n = int(get())
	l = get()
	ans = 10 ** 9
	for c in range(26):
		i = 0
		j = n - 1
		f = 0
		a = 0
		while i < j:
			if l[i] == l[j]:
				i += 1
				j -= 1
			elif l[i] == chr(97 + c):
				i += 1
				a += 1
			elif l[j] == chr(97 + c):
				j -= 1
				a += 1
			else:
				f = 1
				break
		if f == 0:
			ans = min(ans, a)
	if ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


def judge(s, c):
	l = 0
	r = len(s) - 1
	cnt = 0
	while l < r:
		if s[l] == s[r]:
			r -= 1
			l += 1
		elif s[l] == c:
			cnt += 1
			l += 1
		elif s[r] == c:
			cnt += 1
			r -= 1
		else:
			return 100000.0
	return cnt
for _ in range(int(input())):
	n = int(input())
	tmp = input()
	cnt = 100000.0
	for i in range(26):
		cnt = min(cnt, judge(tmp, chr(ord('a') + i)))
	print(-1) if cnt == 100000.0 else print(cnt)


R = lambda : map(int, input().split())
p = print
(t,) = R()
while t:
	t -= 1
	(n,) = R()
	s = input()
	ans = 1000000000.0
	for i in list(map(chr, range(97, 123))):
		currans = 0
		l = 0
		r = n - 1
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == i:
				currans += 1
				l += 1
			elif s[r] == i:
				currans += 1
				r -= 1
			else:
				currans = 1000000000.0
				break
		ans = min(currans, ans)
	if ans == 1000000000.0:
		ans = -1
	p(ans)


from typing import *

def minRemoveToMakePalindrome(n: int, s: str) -> int:
	ref = ord('a')
	mn = float('inf')
	for i in range(26):
		letter = chr(ref + i)
		(l, r) = (0, n - 1)
		isPalin = True
		remove = 0
		while l <= r:
			(cl, cr) = (s[l], s[r])
			if cl == cr:
				l += 1
				r -= 1
				continue
			if cl == letter:
				l += 1
				remove += 1
				continue
			if cr == letter:
				r -= 1
				remove += 1
				continue
			isPalin = False
			break
		if isPalin:
			mn = min(mn, remove)
	return -1 if mn == float('inf') else mn
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(minRemoveToMakePalindrome(n, s))


from string import ascii_lowercase
t = int(input())

def num_of_removals(s, ch):
	i = 0
	j = len(s) - 1
	ans = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] == ch and s[j] != ch:
			i += 1
			ans += 1
		elif s[j] == ch and s[i] != ch:
			j -= 1
			ans += 1
		else:
			return -1
	return ans
for i in range(t):
	n = int(input())
	s = input()
	S = [ch for ch in s]
	ans = n + 1000
	alphabets = []
	for c in ascii_lowercase:
		if num_of_removals(S, c) == -1:
			continue
		else:
			ans = min(ans, num_of_removals(S, c))
	if ans == n + 1000:
		print(-1)
	else:
		print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = s[:-1]
	if s == s[::-1]:
		print(0)
		continue
	res = float('inf')
	for ch in set(s):
		ss = s.replace(ch, '')
		if ss != ss[::-1]:
			continue
		(i, j, erase) = (0, len(s) - 1, 0)
		(ii, jj) = (0, len(ss) - 1)
		while i < j and ii <= jj:
			lch = 0
			while s[i] != ss[ii]:
				if s[i] == ch:
					lch += 1
				i += 1
			rch = 0
			while s[j] != ss[jj]:
				if s[j] == ch:
					rch += 1
				j -= 1
			erase += lch + rch - min(lch, rch) * 2
			(i, ii) = (i + 1, ii + 1)
			(j, jj) = (j - 1, jj - 1)
		res = min(res, erase)
	if res == float('inf'):
		print(-1)
	else:
		print(res)


import math
a = int(input())
for i in range(a):
	s = int(input())
	z = input()
	mini = math.inf
	for i in range(26):
		l = 0
		r = len(z) - 1
		g1 = 0
		flag = 0
		while l < r:
			if z[l] == z[r]:
				l += 1
				r -= 1
				continue
			if ord(z[l]) == 97 + i:
				g1 += 1
				l += 1
			elif ord(z[r]) == 97 + i:
				g1 += 1
				r -= 1
			else:
				flag = 1
				break
		if flag == 0:
			mini = min(mini, g1)
	if mini == math.inf:
		print(-1)
	else:
		print(mini)


x = [chr(97 + i) for i in range(26)]
for i in range(int(input())):
	n = int(input())
	s = input()
	ans = 10 ** 8
	for c in x:
		i = 0
		j = n - 1
		curr = 0
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == c:
				i += 1
				curr += 1
			elif s[j] == c:
				j -= 1
				curr += 1
			else:
				curr = 10 ** 8
				break
		ans = min(ans, curr)
	if ans == 10 ** 8:
		print(-1)
	else:
		print(ans)


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')

def solve():
	(n,) = maps()
	s = input()
	if s == s[::-1]:
		print(0)
		return
	cnt = [0] * 26
	for i in s:
		cnt[ord(i) - ord('a')] += 1
	lowercase = 'abcdefghijklmnopqrstuvwxyz'
	ans = 0
	ok = False
	for i in range(26):
		x = lowercase[i]
		ss = s.replace(x, '')
		if ss == ss[::-1]:
			ok = True
			(ii, jj) = (0, n - 1)
			t = 0
			pp = True
			while ii < jj:
				if s[ii] != s[jj]:
					if s[ii] == lowercase[i]:
						ii += 1
						t += 1
					elif s[jj] == lowercase[i]:
						jj -= 1
						t += 1
					else:
						pp = False
						break
				else:
					ii += 1
					jj -= 1
			if pp:
				ans = max(ans, n - t)
	if ok:
		print(n - ans)
	else:
		print(-1)
for _ in range(*maps()):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = n
	for k in range(26):
		(i, j) = (0, n - 1)
		temp = 0
		flag = True
		while i < j:
			if s[i] != s[j]:
				if ord(s[i]) - ord('a') == k or ord(s[j]) - ord('a') == k:
					temp += 1
					if ord(s[i]) - ord('a') == k:
						i += 1
					else:
						j -= 1
				else:
					flag = False
					break
			else:
				i += 1
				j -= 1
		if flag:
			ans = min(ans, temp)
	if ans == n:
		print(-1)
	else:
		print(ans)


def answer():
	N = int(input())
	s = list(input())
	str_list = set(s)
	if all((s[i] == s[N - 1 - i] for i in range(N // 2 + 1))):
		print(0)
		return

	def num_count(x):
		ts = []
		d = dict()
		cnt = 0
		for i in range(N):
			if s[i] != x:
				ts.append(s[i])
				d[cnt] = i
				cnt += 1
		n = len(ts)
		if any((ts[i] != ts[n - 1 - i] for i in range(n // 2 + 1))):
			return -1
		ans = N - n
		ans -= 2 * min(d[0], N - d[n - 1] - 1)
		if n % 2 == 0:
			m = n // 2
			if m == 1:
				ans -= d[1] - d[0] - 1
				return ans
			ans -= d[m] - d[m - 1] - 1
			for j in range(m - 1):
				ans -= 2 * min(d[m - 1 - j] - d[m - 2 - j] - 1, d[m + 1 + j] - d[m + j] - 1)
		else:
			m = n // 2
			if m == 0:
				return ans
			for j in range(m):
				ans -= 2 * min(d[m - j] - d[m - 1 - j] - 1, d[m + 1 + j] - d[m + j] - 1)
		return ans
	tans = N + 1
	for x in str_list:
		tmp = num_count(x)
		if tmp != -1:
			tans = min(tans, tmp)
		else:
			continue
	if tans == N + 1:
		print(-1)
	else:
		print(tans)
	return
t = int(input())
for _ in range(t):
	answer()


from math import *
from collections import *
import os
from io import BytesIO, IOBase
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 1000000007
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binpow(a, b, m):
	a %= m
	x = 1
	while b > 0:
		if b & 1:
			x = x * a % m
		a = a * a % m
		b >>= 1
	return x

def sakurajima(n):
	d = defaultdict(list)
	if n < 9:
		n = 10
	l = [1] * n
	for i in range(2, int(n ** 0.5) + 1):
		if l[i - 1] == 1:
			for j in range(2 * i, n + 1, i):
				if j % i == 0:
					l[j - 1] = 0
					d[j].append(i)
	return d

def binser(arr, l, r, x):
	while l < r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return mid

def lcm(a, b):
	return a * b // gcd(a, b)

def sod(n):
	l = list(str(n))
	s = 0
	for i in l:
		s += int(i)
	return s

def prime_factors(num):
	l = []
	if num % 2:
		l.append(2)
	while num % 2 == 0:
		num = num / 2
	for i in range(3, int(sqrt(num)) + 1, 2):
		if not num % i:
			l.append(i)
		while num % i == 0:
			num = num / i
	if num > 2:
		l.append(num)
	return l

def factmod(n, p):
	f = defaultdict(int)
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % MOD
	return f

def largestPower(n, p):
	x = 0
	while n:
		n //= p
		x += n
	return x

def modFact(n, p):
	if n >= p:
		return 0
	res = 1
	isPrime = [1] * (n + 1)
	i = 2
	while i * i <= n:
		if isPrime[i]:
			for j in range(2 * i, n, i):
				isPrime[j] = 0
		i += 1
	for i in range(2, n):
		if isPrime[i]:
			k = largestPower(n, i)
			res = res * binpow(i, k, p) % p
	return res

def dfs(ajl, temp, now, vis):
	vis[now] = True
	temp.append(now)
	for i in ajl[now]:
		if not vis[i]:
			temp = dfs(ajl, temp, i, vis)
	return temp

def panda(n, s):
	d = defaultdict(int)
	ans = MOD
	for i in s:
		d[i] += 1
	for x in d:
		(i, j) = (0, n - 1)
		cnt = 0
		fl = 0
		while i < j:
			if s[i] != s[j]:
				if s[i] == x:
					i += 1
					cnt += 1
				elif s[j] == x:
					j -= 1
					cnt += 1
				else:
					fl = 1
					break
			else:
				i += 1
				j -= 1
		if not fl:
			ans = min(ans, cnt)
	if ans != MOD:
		return ans
	return -1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(panda(n, s))


def check_palin(s, c):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] == c:
			i += 1
			continue
		if s[j] == c:
			j -= 1
			continue
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			return False
	return True
T = int(input())
for t in range(T):
	n = int(input())
	s = list(input())
	(i, j) = (0, n - 1)
	while i < j and s[i] == s[j]:
		i += 1
		j -= 1
	if i >= j:
		print(0)
		continue
	p1 = []
	p2 = []
	a = check_palin(s, s[i])
	b = check_palin(s, s[j])
	if a == False and b == False:
		print(-1)
		continue
	ps = [s[i], s[j]]
	sm = 100000
	for p in ps:
		c = 0
		(i, j) = (0, n - 1)
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == p:
				i += 1
				c += 1
			elif s[j] == p:
				j -= 1
				c += 1
			else:
				c = -1
				break
		if c >= 0:
			sm = min(sm, c)
	print(sm)


for _ in range(int(input())):
	n = int(input())
	alpha = input()
	minn = 100000000
	for i in range(97, 123):
		(j, k, f, cnt) = (0, n - 1, 1, 0)
		while j < k:
			if alpha[k] == alpha[j]:
				j += 1
				k -= 1
			elif alpha[k] != chr(i) and alpha[j] != chr(i):
				f = 0
				break
			elif alpha[j] == chr(i):
				j += 1
				cnt += 1
			elif alpha[k] == chr(i):
				k -= 1
				cnt += 1
		if f:
			minn = min(minn, cnt)
	print(minn if minn != 100000000 else -1)


def logic(s):
	n = len(s)
	if n < 2:
		return 0
	else:
		l = 0
		r = n - 1
		while s[l] == s[r] and l < r:
			l += 1
			r -= 1
		s = s[l:r + 1]
		if len(s) < 2:
			return 0
		res1 = fixed(s[:-1], s[-1])
		res2 = fixed(s[1:], s[0])
		r = 1 + min(res1, res2)
		if r < 10 ** 5:
			return r
		return -1

def fixed(s, c):
	n = len(s)
	if n < 2:
		return 0
	l = 0
	r = n - 1
	count = 0
	while l < r:
		l_v = s[l]
		r_v = s[r]
		if l_v == r_v:
			l += 1
			r -= 1
		elif l_v == c:
			count += 1
			l += 1
		elif r_v == c:
			count += 1
			r -= 1
		else:
			break
	if l < r:
		return 10 ** 5
	return count
for w in range(0, int(input())):
	input()
	s = input()
	print(logic(s))


for i in range(int(input())):
	length_s = int(input())
	s = input()
	pal_l_list = []
	for ch in set(s):
		pre_s = s.replace(ch, '')
		length = len(pre_s)
		if pre_s[:length // 2] == pre_s[length:(length + 1) // 2 - 1:-1]:
			counter = 0
			pol_s = [*s]
			i = 0
			while i < len(pol_s) // 2:
				if not pol_s[i] == pol_s[~i] == ch:
					while pol_s[i] == ch:
						pol_s.pop(i)
					while pol_s[~i] == ch:
						pol_s.pop(~i)
				i += 1
			pal_l_list.append(len(pol_s))
	if len(pal_l_list) > 0:
		print(length_s - max(pal_l_list))
	else:
		print(-1)


from sys import stdin, stdout, setrecursionlimit
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	s = S()
	ans = inf
	for i in range(26):
		x = chr(97 + i)
		l = 0
		r = n - 1
		m = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
				continue
			if s[l] == x:
				l += 1
				m += 1
			elif s[r] == x:
				r -= 1
				m += 1
			else:
				m = inf
				break
		ans = min(ans, m)
	print(-1 if ans == inf else ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	ans = 10 ** 9
	f = 0
	for i in range(26):
		c = chr(ord('a') + i)
		i1 = 0
		j = n - 1
		rh = 0
		fh = 1
		while i1 < j:
			if s[i1] == s[j]:
				i1 += 1
				j -= 1
				continue
			elif s[i1] == c:
				i1 += 1
				rh += 1
			elif s[j] == c:
				j -= 1
				rh += 1
			else:
				fh = 0
				break
		if fh:
			f = 1
			ans = min(ans, rh)
	if f:
		print(ans)
	else:
		print(-1)


from sys import stdin, stdout
input = stdin.readline

def output(answer):
	stdout.write('{}\n'.format(answer))
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s[-1] == '\n':
		s = s[:-1]
	d = {}
	for c in s:
		d[c] = True
	maximum = 1000000000.0
	for char in range(26):
		count = 0
		(low, high) = (0, n - 1)
		c = chr(char + 97)
		if c not in d:
			continue
		while low < high:
			if s[low] == s[high]:
				low += 1
				high -= 1
			elif s[low] == c:
				low += 1
				count += 1
			elif s[high] == c:
				high -= 1
				count += 1
			else:
				count = float('inf')
				break
		maximum = min(maximum, count)
	if maximum >= 1000000000:
		output(-1)
	else:
		output(maximum)


from string import ascii_lowercase
cases = int(input())
for _ in range(cases):
	num = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
		continue
	pal = False
	ans = 10 ** 10
	for char in ascii_lowercase:
		new_s = s.replace(char, '')
		if new_s == new_s[::-1]:
			pal = True
			rem_num = 0
			left = 0
			right = num - 1
			while left < right:
				if s[left] != s[right]:
					if s[left] == char:
						left += 1
					else:
						right -= 1
					rem_num += 1
				else:
					right -= 1
					left += 1
			ans = min(ans, rem_num)
	if not pal:
		print(-1)
	else:
		print(ans)


from math import factorial
for _ in range(int(input())):
	size = int(input())
	st = str(input())
	arr = []
	ans = 0
	ans0 = 0
	ans1 = 0
	for ind in range(size):
		arr.append(st[ind])
	for ind in range(size // 2):
		if arr[ind] != arr[size - ind - 1]:
			ctk0 = arr[ind]
			ctk1 = arr[size - ind - 1]
			ind0 = ind
			ind1 = size - ind - 1
			while ind0 <= ind1:
				if ans0 == int(1e+18):
					break
				if arr[ind0] != arr[ind1]:
					if arr[ind0] == ctk0:
						ans0 += 1
						ind0 += 1
					elif arr[ind1] == ctk0:
						ans0 += 1
						ind1 -= 1
					else:
						ans0 = int(1e+18)
				else:
					ind0 += 1
					ind1 -= 1
			ind0 = ind
			ind1 = size - ind - 1
			while ind0 <= ind1:
				if ans1 == int(1e+18):
					break
				if arr[ind0] != arr[ind1]:
					if arr[ind0] == ctk1:
						ans1 += 1
						ind0 += 1
					elif arr[ind1] == ctk1:
						ans1 += 1
						ind1 -= 1
					else:
						ans1 = int(1e+18)
				else:
					ind0 += 1
					ind1 -= 1
			break
	ans = min(ans1, ans0)
	if ans == int(1e+18):
		print(-1)
	else:
		print(ans)


from sys import stdin, stdout
print = stdout.write
input = stdin.readline

def solve_test():
	n = int(input())
	s = input()[:-1]
	(a, b) = ('', '')
	for i in range(n // 2):
		if s[i] != s[-1 - i]:
			(a, b) = (s[i], s[-1 - i])
			break
	if a == '':
		return 0

	def find_palindromes_removing(char):
		(left, right) = (0, n - 1)
		removals = 0
		while left < right:
			if s[left] != s[right]:
				if s[left] == char:
					left += 1
					removals += 1
				elif s[right] == char:
					right -= 1
					removals += 1
				else:
					return -1
			else:
				left += 1
				right -= 1
		return removals
	(x, y) = (find_palindromes_removing(a), find_palindromes_removing(b))
	z = min(x, y)
	if z == -1:
		z = max(x, y)
	return z

def main(args=None):
	tests = int(input())
	for _ in range(tests):
		print(f'{solve_test()}\n')
main()


import sys
input = sys.stdin.readline

def func(nn, ss, char):
	val = 0
	string = s.replace(char, '')
	if string.split() == string[::-1].split():
		i = 0
		j = nn - 1
		while i <= j:
			if ss[i] == char:
				if ss[i] != ss[j]:
					i += 1
					val += 1
				else:
					i += 1
					j -= 1
			elif ss[j] == char:
				if ss[j] != ss[i]:
					j -= 1
					val += 1
			else:
				i += 1
				j -= 1
		return val
	return 1e+18
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	char = set(s)
	ans = 1e+18
	for i in char:
		ans = min(ans, func(n, s, i))
	if ans == 1e+18:
		print(-1)
	else:
		print(ans)


def solve(a, c, n):
	res = 0
	l = 0
	r = n - 1
	while l < r:
		if a[l] != a[r]:
			if a[l] == c:
				res += 1
				l += 1
			elif a[r] == c:
				res += 1
				r -= 1
			else:
				return 10 ** 10
		else:
			l += 1
			r -= 1
	return res
for _ in range(int(input())):
	n = int(input())
	a = input()
	ans = 10 ** 10
	for i in range(26):
		ans = min(ans, solve(a, chr(97 + i), n))
	if ans == 10 ** 10:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	point1 = 0
	point2 = n - 1
	while point2 > point1 and s[point1] == s[point2]:
		point1 += 1
		point2 -= 1
	if point2 <= point1:
		print(0)
	else:
		char1 = s[point1]
		char2 = s[point2]
		actp1 = point1
		actp2 = point2
		count1 = 0
		valid1 = True
		while actp2 > actp1:
			if s[actp1] == s[actp2]:
				actp1 += 1
				actp2 -= 1
			elif s[actp1] == char1:
				actp1 += 1
				count1 += 1
			elif s[actp2] == char1:
				actp2 -= 1
				count1 += 1
			else:
				valid1 = False
				actp1 = 1
				actp2 = 0
		if not valid1:
			count1 = n + 1
		actp1 = point1
		actp2 = point2
		count2 = 0
		valid2 = True
		while actp2 > actp1:
			if s[actp1] == s[actp2]:
				actp1 += 1
				actp2 -= 1
			elif s[actp1] == char2:
				actp1 += 1
				count2 += 1
			elif s[actp2] == char2:
				actp2 -= 1
				count2 += 1
			else:
				valid2 = False
				actp1 = 1
				actp2 = 0
		if not valid2:
			count2 = n + 1
		ans = min([count1, count2])
		if ans > n:
			print(-1)
		else:
			print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = -1
	l = list(s)
	ch = set(l)
	for c in ch:
		i = 0
		j = n - 1
		left = 0
		right = 0
		palindrome = True
		musterase = 0
		while i <= j:
			if s[i] == c:
				i += 1
				left += 1
				continue
			if s[j] == c:
				j -= 1
				right += 1
				continue
			if s[i] != s[j]:
				palindrome = False
				break
			musterase += abs(left - right)
			left = 0
			right = 0
			i += 1
			j -= 1
		if not palindrome:
			continue
		if ans < 0:
			ans = musterase
		else:
			ans = min(ans, musterase)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	left = 0
	right = n - 1
	ch = None
	ch2 = None
	while left < right:
		if s[left] == s[right]:
			left += 1
			right -= 1
		else:
			ch = s[left]
			ch2 = s[right]
			break
	if ch == None and ch2 == None:
		print(0)
		continue
	else:
		count = 1
		l2 = left + 1
		r2 = right
		p1 = True
		while l2 < r2:
			if s[l2] == s[r2]:
				l2 += 1
				r2 -= 1
			elif s[l2] == ch:
				l2 += 1
				count += 1
			elif s[r2] == ch:
				r2 -= 1
				count += 1
			else:
				p1 = False
				break
		count2 = 1
		r2 = right - 1
		l2 = left
		p2 = True
		while l2 < r2:
			if s[l2] == s[r2]:
				l2 += 1
				r2 -= 1
			elif s[l2] == ch2:
				l2 += 1
				count2 += 1
			elif s[r2] == ch2:
				r2 -= 1
				count2 += 1
			else:
				p2 = False
				break
		if p1 and p2:
			print(min(count, count2))
		elif p1:
			print(count)
		elif p2:
			print(count2)
		else:
			print(-1)


import sys
readline = sys.stdin.readline
T = int(readline())
for t in range(T):
	N = int(readline())
	S = [ord(s) - 97 for s in readline().rstrip()]
	ans = 1 << 30
	for s in range(26):
		(i, j) = (0, N)
		cnt = 0
		while j - i >= 2:
			if S[i] == S[j - 1]:
				i += 1
				j -= 1
			elif S[i] == s:
				i += 1
				cnt += 1
			elif S[j - 1] == s:
				j -= 1
				cnt += 1
			else:
				break
		else:
			ans = min(ans, cnt)
	if ans == 1 << 30:
		ans = -1
	print(ans)


t = int(input())
alpha = [chr(i) for i in range(ord('a'), ord('z') + 1)]

def is_palind(str_a, word):
	clean = str_a.replace(word, '')
	center_elem = len(clean) // 2
	return clean == clean[::-1]

def find_min_words(palin, word):
	ind_r = 0
	ind_l = len(palin) - 1
	count = 0
	while ind_r < ind_l:
		if palin[ind_r] == palin[ind_l]:
			ind_r += 1
			ind_l -= 1
		else:
			count += 1
			if palin[ind_r] == word:
				ind_r += 1
			else:
				ind_l -= 1
	return count
for t_i in range(t):
	n = int(input())
	s = input()
	count_word = 1000000000.0
	for word in alpha:
		if is_palind(s, word) == False:
			continue
		else:
			count_word = min(count_word, find_min_words(s, word))
	if count_word == 1000000000.0:
		print(-1)
	else:
		print(count_word)


def pal(s, x):
	i = 0
	j = len(s) - 1
	k = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] != x and s[j] != x:
			return (False, 0)
		elif s[i] == x:
			k += 1
			i += 1
		elif s[j] == x:
			k += 1
			j -= 1
	return (True, k)
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
	else:
		s = list(s)
		i = 0
		j = n - 1
		while s[i] == s[j]:
			i += 1
			j -= 1
		(r, k1) = pal(s, s[i])
		(rr, k2) = pal(s, s[j])
		if not r and (not rr):
			print(-1)
		else:
			if r:
				ans = k1
				if rr:
					ans = min(k1, k2)
			else:
				ans = k2
			print(ans)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for i in range(int(input())):
	n = int(input())
	st = input()
	val = set()
	for i in st:
		if i not in val:
			val.add(i)
	ans = float('inf')
	for elm in val:
		i = 0
		j = n - 1
		cnt = 0
		flag = 1
		while i < j:
			if st[i] == st[j]:
				i += 1
				j -= 1
				continue
			elif st[i] == elm:
				cnt += 1
				i += 1
			elif st[j] == elm:
				cnt += 1
				j -= 1
			else:
				flag = 0
				break
		if flag == 1:
			ans = min(ans, cnt)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)


def palindrome(x, word) -> int:
	(beg, fin) = (0, len(word) - 1)
	changes = 0
	while beg <= fin:
		if word[beg] == word[fin]:
			(beg, fin) = (beg + 1, fin - 1)
			continue
		if word[beg] == x:
			beg += 1
			changes += 1
			continue
		if word[fin] == x:
			fin -= 1
			changes += 1
			continue
		return -1
	return changes

def solve():
	n = int(input())
	arr = input()
	letters = map(chr, range(97, 97 + 26))
	results = [palindrome(letter, arr) for letter in letters]
	if all(map(lambda x: x == -1, results)):
		return -1
	return min(filter(lambda x: x > -1, results))
for _ in range(int(input())):
	print(solve())


def checkpallindorme(arr):
	l = len(arr) - 1
	f = 0
	while f <= l:
		if arr[f] != arr[l]:
			return False
		l -= 1
		f += 1
	return True
for _ in range(int(input())):
	n = int(input())
	arr = [c for c in input()]
	if checkpallindorme(arr):
		print(0)
	else:
		ans = float('inf')
		ss = 'abcdefghijklmnopqrstuvwxyz'
		for s in ss:
			f = 0
			l = len(arr) - 1
			count = 0
			while f <= l:
				if arr[f] == arr[l]:
					f += 1
					l -= 1
					continue
				if arr[f] == s:
					count += 1
					f += 1
					continue
				if arr[l] == s:
					count += 1
					l -= 1
					continue
				count = float('inf')
				break
			ans = min(ans, count)
		if ans == float('inf'):
			print(-1)
		else:
			print(ans)


def isOno(s, a):
	s1 = [i for i in s if i != a]
	d = len(s1)
	for i in range(d // 2):
		if s1[i] != s1[d - 1 - i]:
			return False
	return True

def count(s, a):
	c = 0
	b = 0
	e = len(s) - 1
	while b != e and b < e:
		if s[b] == s[e]:
			b = b + 1
			e = e - 1
		else:
			if s[b] == a:
				b = b + 1
			else:
				e = e - 1
			c = c + 1
	return c
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	checked = []
	ono = []
	res = []
	for i in st:
		if i not in checked:
			checked.append(i)
	for i in checked:
		if isOno(st, i):
			ono.append(i)
			res.append(count(st, i))
	if res == []:
		print(-1)
	else:
		print(min(res))


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
mod = 998244353
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	s = ips()
	arr = list(s)
	if s == s[::-1]:
		ans = 0
	else:
		opt = []
		ans = []
		for i in range(n // 2):
			if s[i] == s[n - i - 1]:
				pass
			else:
				opt.append(s[i])
				opt.append(s[n - i - 1])
				break
		for x in opt:
			pt = 0
			pt2 = n - 1
			f = True
			cur = 0
			while pt < pt2:
				if arr[pt] == arr[pt2]:
					pt += 1
					pt2 -= 1
				elif arr[pt] == x:
					pt += 1
					cur += 1
				elif arr[pt2] == x:
					pt2 -= 1
					cur += 1
				else:
					f = False
					break
			if f:
				ans.append(cur)
		if len(ans) == 0:
			ans = -1
		else:
			ans = min(ans)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lptr = 0
	rptr = n - 1
	while lptr <= rptr:
		if s[lptr] != s[rptr]:
			x = s[lptr]
			y = s[rptr]
			break
		lptr += 1
		rptr -= 1
	cntx = 0
	cnty = 0
	flag1 = False
	flag2 = False
	while lptr <= rptr:
		if s[lptr] != s[rptr]:
			if s[lptr] == x:
				cntx += 1
				lptr += 1
			elif s[rptr] == x:
				cntx += 1
				rptr -= 1
			else:
				flag1 = True
				break
		else:
			lptr += 1
			rptr -= 1
	lptr = 0
	rptr = n - 1
	while lptr <= rptr:
		if s[lptr] != s[rptr]:
			if s[lptr] == y:
				cnty += 1
				lptr += 1
			elif s[rptr] == y:
				cnty += 1
				rptr -= 1
			else:
				flag2 = True
				break
		else:
			lptr += 1
			rptr -= 1
	if flag1 and flag2:
		print(-1)
	elif not flag1 and (not flag2):
		print(min(cntx, cnty))
	elif flag1:
		print(cnty)
	else:
		print(cntx)


def read_line():
	return [int(x) for x in input().split()]

def read_int():
	return int(input())

def solve():
	n = read_int()
	s = input()
	res = 1000000000.0
	for k in range(26):
		ch = chr(k + ord('a'))
		(i, j, ops) = (0, n - 1, 0)
		flag = True
		while i < j:
			if s[i] != s[j]:
				if ch != s[i] and ch != s[j]:
					flag = False
					break
				if s[i] == ch:
					i += 1
				else:
					j -= 1
				ops += 1
			else:
				i += 1
				j -= 1
		if flag:
			res = min(res, ops)
	if res == 1000000000.0:
		print(-1)
	else:
		print(res)
t = read_int()
while t > 0:
	solve()
	t -= 1


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	n = int(input())
	arr = list(input())
	unique = set(arr)
	ans = float('inf')
	for word in unique:
		i = 0
		j = len(arr) - 1
		t = 0
		while i < j:
			if arr[i] != arr[j]:
				if arr[i] == word or arr[j] == word:
					if arr[i] == word:
						i += 1
						t += 1
					elif arr[j] == word:
						j -= 1
						t += 1
				else:
					break
			else:
				i += 1
				j -= 1
		if i >= j:
			ans = min(ans, t)
	if ans != float('inf'):
		print(ans)
	else:
		print(-1)
for _ in range(int(input())):
	solve()


T = int(input())
for test in range(1, T + 1):
	N = int(input())
	S = input().strip()
	(leftAns, rightAns) = (0, 0)
	(leftRm, rightRm) = (None, None)
	(left, right) = (0, N - 1)
	while left <= right:
		if S[left] != S[right]:
			if leftRm == None:
				leftRm = S[left]
			if leftRm == S[left]:
				leftAns += 1
				left += 1
			elif leftRm == S[right]:
				leftAns += 1
				right -= 1
			else:
				leftAns = N + 1
				break
		else:
			left += 1
			right -= 1
	(left, right) = (0, N - 1)
	while left <= right:
		if S[left] != S[right]:
			if rightRm == None:
				rightRm = S[right]
			if rightRm == S[left]:
				rightAns += 1
				left += 1
			elif rightRm == S[right]:
				rightAns += 1
				right -= 1
			else:
				rightAns = N + 1
				break
		else:
			left += 1
			right -= 1
	ans = min(leftAns, rightAns)
	print(ans if ans <= N else -1)


import sys, os.path
if os.path.exists('inp.txt'):
	sys.stdin = open('inp.txt', 'r')
	sys.stdout = open('out.txt', 'w')

def solve(string, n):
	s = set()
	for i in string:
		if i not in s:
			s.add(i)
	ans = 99999999
	for character in s:
		i = 0
		j = n - 1
		change = 0
		while i < j:
			if string[i] != string[j]:
				if string[i] == character:
					i += 1
					change += 1
				elif string[j] == character:
					j -= 1
					change += 1
				else:
					change = float('inf')
					break
			else:
				i += 1
				j -= 1
		ans = min(ans, change)
	if ans == 99999999:
		return -1
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	print(solve(string, n))


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	ans = 0
	for i in range(0, n):
		if s[i] != s[n - 1 - i]:
			l1 = s[i]
			l2 = s[n - 1 - i]
			ans = -1
	if ans == -1:
		for l in [l1, l2]:
			c = 0
			i = 0
			j = n - 1
			while i < j:
				if s[i] != s[j]:
					if s[i] != l and s[j] != l:
						c = -1
						break
					elif s[i] == l:
						i = i + 1
						c = c + 1
					else:
						j = j - 1
						c = c + 1
				else:
					i = i + 1
					j = j - 1
			if ans == -1:
				ans = c
			elif c != -1:
				ans = min(ans, c)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ok = True
	for i in range(n):
		if s[i] != s[n - i - 1]:
			ok = False
			k = i
			k2 = n - i - 1
	if ok:
		print(0)
		continue
	pivot1 = s[k]
	pivot2 = s[n - k - 1]
	st = ''
	m1 = 10 ** 9
	m2 = 10 ** 9
	for i in range(n):
		if s[i] != pivot1:
			st += s[i]
	if st == st[::-1]:
		m1 = 0
		i = 0
		j = n - 1
		while i < j:
			if s[i] != s[j]:
				if s[i] == pivot1:
					i += 1
					m1 += 1
				else:
					j -= 1
					m1 += 1
			else:
				i += 1
				j -= 1
	st = ''
	for i in range(n):
		if s[i] != pivot2:
			st += s[i]
	if st == st[::-1]:
		m2 = 0
		i = 0
		j = n - 1
		while i < j:
			if s[i] != s[j]:
				if s[i] == pivot2:
					i += 1
					m2 += 1
				else:
					j -= 1
					m2 += 1
			else:
				i += 1
				j -= 1
	if m1 == 10 ** 9 and m2 == 10 ** 9:
		print(-1)
		continue
	print(min(m1, m2))


import math
import os
import sys
from sys import *
from decimal import *
from io import BytesIO, IOBase
import threading
from itertools import *
from collections import *
from array import *
import random
M = 10 ** 9 + 7
import heapq
import bisect
from functools import lru_cache
from queue import PriorityQueue
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] == key:
			return mid
		if arr[mid] <= key:
			left = mid + 1
		else:
			right = mid - 1
	return -1

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def luckynumber(x, n, a):
	if x > 0:
		a.append(x)
	if x > 10 ** 9:
		return a
	elif x < 1000000000000.0:
		luckynumber(x * 10 + 4, n, a)
		luckynumber(x * 10 + 7, n, a)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def query1(l, r):
	if l >= r:
		return -1
	print('?', l + 1, r + 1)
	sys.stdout.flush()
	return int(input()) - 1

def answer(p):
	print('!', p + 1)
	sys.stdout.flush()
	exit()

def rse(arr, n):
	stack = []
	ans = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			ans.append(n)
		else:
			while len(stack) != 0:
				if stack[-1][0] >= arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(n)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	ans.reverse()
	return ans

def lse(arr, n):
	stack = []
	ans = []
	for i in range(n):
		if len(stack) == 0:
			ans.append(-1)
		else:
			while len(stack) != 0:
				if stack[-1][0] >= arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(-1)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	return ans

def mah(arr):
	max1 = 0
	p = rse(arr, len(arr))
	q = lse(arr, len(arr))
	for i in range(len(arr)):
		a = (p[i] - q[i] - 1) * arr[i]
		max1 = max(a, max1)
	return max1

def maxSumIS(arr, n):
	msis = arr.copy()
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j] and msis[i] < msis[j] + arr[i]:
				msis[i] = msis[j] + arr[i]
	c = max(msis)
	p = 5
	return c

def binarysearch2(arr, target):
	lo = 0
	hi = len(arr) - 1
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] == target:
			if mid != len(arr) - 1:
				if arr[mid + 1] != target:
					return mid
				else:
					lo += 1
			else:
				return mid
			continue
		if arr[mid] > target:
			hi = mid - 1
		else:
			lo = mid + 1

def nge(arr, n):
	stack = []
	ans = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			ans.append(-1)
		else:
			while len(stack) > 0:
				if stack[-1][0] < arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(-1)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	ans.reverse()
	return ans

def alperm(nums, path, result):
	if not nums:
		result.add(tuple(path))
		return
	for i in range(0, len(nums)):
		alperm(nums[:i] + nums[i + 1:], path + [nums[i]], result)
	return result

def minsum(arr, n, m, res, l):
	if n == 1 and m == 1:
		res += arr[0][0]
		l.append(res)
	else:
		if n != 1:
			p = res + arr[n - 1][m - 1]
			minsum(arr, n - 1, m, p, l)
		if m != 1:
			p = res + arr[n - 1][m - 1]
			minsum(arr, n, m - 1, p, l)
	return min(l)

def find_shortest_path(graph, start, end, path):
	path = path + [start]
	if start == end:
		return path
	if start not in graph:
		return None
	shortest = None
	for node in graph[start]:
		if node not in path:
			newpath = find_shortest_path(graph, node, end, path)
			if newpath:
				if not shortest or len(newpath) < len(shortest):
					shortest = newpath
	return shortest

def test(n, d):
	a = random.randint(1, n - 2)
	p = pow(a, d, n)
	if p == 1 or p == n - 1:
		return True
	while d != n - 1:
		d *= 2
		p = pow(p, 2, n)
		if p == n - 1:
			return True
	return False

def isprime(n):
	if n == 1:
		return False
	if n == 2:
		return True
	if n == 3:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for i in range(5):
		if test(n, d) == False:
			return False
	return True

def muin(a, m):
	(x, y, mo) = (1, 0, m)
	if m == 1:
		return 0
	while m > 0:
		(x, y) = (y, x - a // m * y)
		(a, m) = (m, a % m)
	if x < 0:
		return mo + x
	else:
		return x

def good(l, c):
	ch = chr(c)
	if len(l) == 1:
		return 1 if ch != l[0] else 0
	k = len(l) // 2
	lm = k - l[:k].count(ch) + good(l[k:], c + 1)
	rm = k - l[k:].count(ch) + good(l[:k], c + 1)
	return min(lm, rm)

def facto(fact):
	(fact[0], fact[1]) = (1, 1)
	for i in range(2, 10 ** 6 + 1):
		fact[i] = fact[i - 1] * i % M

def comb(n, r, fact):
	return fact[n] * pow(fact[n - r] * fact[r], M - 2, M) % M

def numberToBase(n, b):
	if n == 0:
		return 0
	digits = []
	while n:
		digits.append(n % b)
		n //= b
	return sum(digits)

def main():
	t = 1
	t = int(input())
	for tc in range(1, t + 1):
		n = inpu()
		s = inp()
		ans = float('inf')
		l = set(s)
		for i_ in l:
			i = 0
			j = len(s) - 1
			min1 = 0
			while i < j:
				if s[i] == s[j]:
					i += 1
					j -= 1
					continue
				elif s[i] == i_:
					min1 += 1
					i += 1
				elif s[j] == i_:
					min1 += 1
					j -= 1
				else:
					min1 = float('inf')
					break
			ans = min(ans, min1)
		if ans == float('inf'):
			print(-1)
		else:
			print(ans)
main()


import math
x = int(input())
for i in range(x):
	y = int(input())
	a = input()
	strt = 0
	end = y - 1
	strt1 = 0
	end1 = y - 1
	ans1 = 0
	ans2 = 0
	flag1 = True
	flag2 = True
	count = 0
	count1 = 0
	while strt < end:
		if a[strt] != a[end] and count == 0:
			x = a[end]
			count = 1
			end -= 1
			ans1 += 1
		elif a[strt] != a[end]:
			if a[strt] == x:
				strt += 1
				ans1 += 1
			elif a[end] == x:
				end -= 1
				ans1 += 1
			else:
				flag1 = False
				break
		else:
			strt += 1
			end -= 1
	while strt1 < end1:
		if a[strt1] != a[end1] and count1 == 0:
			x = a[strt1]
			count1 = 1
			strt1 += 1
			ans2 += 1
		elif a[strt1] != a[end1]:
			if a[strt1] == x:
				strt1 += 1
				ans2 += 1
			elif a[end1] == x:
				end1 -= 1
				ans2 += 1
			else:
				flag2 = False
				break
		else:
			strt1 += 1
			end1 -= 1
	if flag1 == False and flag2 == False:
		print(-1)
	elif flag1 == False and flag2 == True:
		print(ans2)
	elif flag1 == True and flag2 == False:
		print(ans1)
	else:
		print(min(ans1, ans2))


import os
import sys
from io import BytesIO, IOBase
from math import cos, pi, ceil, pi, tan, floor, gcd, sqrt, log2, factorial, log10
from collections import Counter
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase
from statistics import mean, median, mode
from bisect import *
alpha = ascii_lowercase
beta = ascii_uppercase

def nextPowerOf2(n):
	p = 1
	if n and (not n & n - 1):
		return n
	while p < n:
		p <<= 1
	return p

def isComposite(n):
	if n <= 1:
		return False
	if n <= 3:
		return False
	if n % 2 == 0 or n % 3 == 0:
		return True
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return True
		i = i + 6
	return False

def get_Divisors(n):
	arr = []
	i = 1
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				arr.append(i)
			else:
				arr.append(i)
				arr.append(n // i)
		i = i + 1
	return arr

def isprime(n):
	if n == 1:
		return 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 0
		i += 1
	return 1

def Sieve(n):
	prime = [True for i in range(n + 1)]
	prime[0] = False
	prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def create_matrix(n, m):
	mat = [[] for i in range(n)]
	for i in range(n):
		for j in range(m):
			mat[i].append(0)
	return mat

def main():
	for ttt in range(int(input())):
		n = int(input())
		s = input().strip()
		ans = n + 1
		for i in range(26):
			l = 0
			r = n - 1
			cc = 0
			while l < r:
				if s[l] == s[r]:
					l += 1
					r -= 1
				elif s[l] == chr(i + ord('a')):
					cc += 1
					l += 1
				elif s[r] == chr(i + ord('a')):
					cc += 1
					r -= 1
				else:
					cc = n + 1
					break
			ans = min(ans, cc)
		if ans == n + 1:
			print(-1)
		else:
			print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	res = -1
	for i in range(26):
		x = chr(i + 97)
		(j, k) = (0, len(s) - 1)
		c = 0
		while k >= j:
			if s[j] == s[k]:
				j += 1
				k -= 1
			elif s[j] == x:
				j += 1
				c += 1
			elif s[k] == x:
				k -= 1
				c += 1
			else:
				break
		if j > k and (res == -1 or res > c):
			res = c
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = 10 ** 9
	for i in range(26):
		l = 0
		r = n - 1
		co = 0
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == chr(int(ord('a')) + i):
				l += 1
				co += 1
			elif s[r] == chr(int(ord('a')) + i):
				r -= 1
				co += 1
			else:
				co = 10 ** 9
				break
		ans = min(co, ans)
	if ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
from math import inf
from string import ascii_lowercase
ri = lambda : map(int, input().split())
ro = lambda : int(input())

def solve():
	n = ro()
	s = input()
	ans = inf
	for c in ascii_lowercase:
		curr = 0
		i = 0
		j = n - 1
		while i <= j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == c:
				i += 1
				curr += 1
			elif s[j] == c:
				j -= 1
				curr += 1
			else:
				curr = inf
				break
		ans = min(ans, curr)
	if ans == inf:
		print(-1)
	else:
		print(ans)
t = 1
t = int(input())
while t:
	t -= 1
	solve()


import sys
from collections import deque

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

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

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	s = list(SI())
	ans = -1
	for i in range(26):
		temp = chr(i + 97)
		count = 0
		tempS = s[:]
		for j in range(len(s)):
			if s[j] == temp:
				count += 1
				tempS[j] = ''
		checkTemp = list(''.join(tempS))
		if checkTemp == checkTemp[::-1]:
			if len(checkTemp) % 2 == 1:
				l = r = len(checkTemp) // 2
			else:
				l = len(checkTemp) // 2 - 1
				r = len(checkTemp) // 2
			newL = -1
			newR = 0
			c = -1
			for j in range(len(s)):
				if tempS[j] != '':
					c += 1
				if c == l and newL == -1:
					newL = j
				if c == r:
					newR = j
					break
			l = newL
			r = newR
			if l != r:
				count -= r - l - 1
			l -= 1
			r += 1
			while l >= 0 and r < len(tempS):
				if tempS[l] == tempS[r] == '':
					count -= 2
					l -= 1
					r += 1
				elif tempS[l] == '':
					l -= 1
				elif tempS[r] == '':
					r += 1
				else:
					l -= 1
					r += 1
			if ans == -1:
				ans = count
			else:
				ans = min(ans, count)
	print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, S):
	ans = INF
	for c in 'abcdefghijklmnopqrstuvwxyz':
		i = 0
		j = N - 1
		n = 0
		while i < j:
			if S[i] != S[j]:
				if S[i] == c:
					i += 1
					n += 1
				elif S[j] == c:
					j -= 1
					n += 1
				else:
					n = INF
					break
			else:
				i += 1
				j -= 1
		ans = min(ans, n)
	if ans == INF:
		return -1
	return ans
T0 = int(input())
for _ in range(T0):
	N = int(input())
	S = input()
	print(solve(N, S))


t = int(input())
for e in range(t):
	n = int(input())
	s = input()
	if s == s[::-1]:
		print(0)
	else:
		h = {}
		for i in s:
			h[i] = 0
		mn = 1000000
		for k in h:
			s1 = ''
			p1 = 0
			p2 = len(s) - 1
			c = 0
			while p1 <= p2:
				if s[p1] == s[p2]:
					p1 += 1
					p2 -= 1
				elif s[p1] != k and s[p2] != k:
					c = 1000000
					break
				elif s[p1] == k:
					p1 += 1
					c += 1
				elif s[p2] == k:
					p2 -= 1
					c += 1
			mn = min(mn, c)
		if mn > 10 ** 5:
			print(-1)
		else:
			print(mn)


t = int(input())
import math
while t:
	n = int(input())
	s = input()
	count = 0
	count_list = []
	char_set = set(s)
	for char in char_set:
		left = 0
		right = n - 1
		count = 0
		while left <= right:
			if s[left] != s[right] and char == s[left]:
				count += 1
				left += 1
			elif s[left] != s[right] and char == s[right]:
				count += 1
				right -= 1
			elif s[left] == s[right]:
				left += 1
				right -= 1
			else:
				count = math.inf
				break
		count_list.append(count)
	min_count = min(count_list)
	if not count_list or min_count == math.inf:
		print(-1)
	else:
		print(min_count)
	t -= 1


def check(p, s, a):
	(l, r) = (0, len(s) - 1)
	ans = len(p)
	while l < r:
		if s[l] == a and s[r] == a:
			ans += 2
			l += 1
			r -= 1
		elif s[l] == a:
			l += 1
		elif s[r] == a:
			r -= 1
		else:
			l += 1
			r -= 1
	if l == r and s[l] == a:
		ans += 1
	return ans
INF = float('inf')
for _ in range(int(input())):
	N = int(input())
	S = input()
	if S == S[::-1]:
		print(0)
		continue
	ans = INF
	for a in [chr(c) for c in range(ord('a'), ord('z') + 1)]:
		tmp = [c for c in S if c != a]
		if tmp == tmp[::-1]:
			maxlen = check(tmp, S, a)
			ans = min(ans, N - maxlen)
	print(ans if ans != INF else -1)


def check(string, char):
	i = 0
	j = len(string) - 1
	c = 0
	while i < j:
		if string[i] == string[j]:
			i += 1
			j -= 1
		elif string[i] == char:
			i += 1
			c += 1
		elif string[j] == char:
			j -= 1
			c += 1
		else:
			return float('inf')
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	string = str(input())
	mini = float('inf')
	for ascii in range(97, 123):
		mini = min(check(string, chr(ascii)), mini)
	if mini != float('inf'):
		ans = mini
	else:
		ans = -1
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	s = str(input())
	ans = n + 1
	for i in range(0, 26):
		l = 0
		r = n - 1
		cnt = 0
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == chr(ord('a') + i):
				cnt += 1
				l += 1
			elif s[r] == chr(ord('a') + i):
				cnt += 1
				r -= 1
			else:
				cnt = n + 1
				break
		ans = min(ans, cnt)
	if ans == n + 1:
		ans = -1
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	lletres = set(s)
	min_cost = float('inf')
	for c in lletres:
		(i, j) = (0, n - 1)
		(pal, cost) = (True, 0)
		while pal and i < j:
			if s[i] != c and s[j] != c:
				pal = s[i] == s[j]
				i += 1
				j -= 1
			if s[i] == c and s[j] != c:
				i += 1
				cost += 1
			if s[i] != c and s[j] == c:
				j -= 1
				cost += 1
			if s[i] == c and s[j] == c:
				i += 1
				j -= 1
		if pal:
			min_cost = min(min_cost, cost)
	print(min_cost if min_cost < float('inf') else -1)


import string

def scarf(s, n):
	best = float('inf')
	for letter in string.ascii_lowercase:
		l = 0
		r = n - 1
		deleted = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
				continue
			if s[l] == letter:
				l += 1
				deleted += 1
				continue
			if s[r] == letter:
				r -= 1
				deleted += 1
				continue
			deleted = float('inf')
			break
		best = min(best, deleted)
	if best == float('inf'):
		best = -1
	return best
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(scarf(s, n))


import bisect
import collections
import copy
import enum
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
sys.setrecursionlimit(3001)
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	ans = float('inf')
	for c in string.ascii_lowercase:
		(st, ed) = (0, n - 1)
		cnt = 0
		while st < ed:
			if s[st] == s[ed]:
				st += 1
				ed -= 1
			elif s[st] == c:
				st += 1
				cnt += 1
			elif s[ed] == c:
				ed -= 1
				cnt += 1
			else:
				cnt = float('inf')
				break
		ans = min(ans, cnt)
	if ans == float('inf'):
		print(-1)
	else:
		print(ans)


from math import *
from math import factorial as fact, comb as ncr
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
li = lambda : list(map(int, input().split()))
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		c = set(s)
		m = n
		for ct in c:
			temp = s.replace(ct, '')
			if temp == temp[::-1]:
				i = 0
				j = n - 1
				c = 0
				while i < j:
					if s[i] != s[j]:
						c += 1
						if s[i] == ct:
							i += 1
						else:
							j -= 1
					else:
						i += 1
						j -= 1
				m = min(m, c)
		print(m if m != n else -1)
solve()


t = int(input())
letters = [chr(ord('a') + i) for i in range(26)]
for _ in range(t):
	n = int(input())
	s = input().strip()
	res = -1
	for c in letters:
		s1 = s.replace(c, '')
		if all((s1[i] == s1[-i - 1] for i in range(len(s1) // 2))):
			(l, r) = (0, n - 1)
			temp = 0
			while r > l:
				if s[l] != c:
					while s[r] != s[l]:
						temp += 1
						r -= 1
				elif s[r] != c:
					while s[l] != s[r]:
						temp += 1
						l += 1
				l += 1
				r -= 1
			if res == -1 or res > temp:
				res = temp
	print(res)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	(p, q) = (0, len(s) - 1)
	while p < q and s[p] == s[q]:
		p += 1
		q -= 1
	if p >= q:
		print(0)
		continue
	left_ans = 0
	left_char = s[p]
	pp = p
	qq = q
	while pp < qq:
		if s[pp] == s[qq]:
			pp += 1
			qq -= 1
		elif s[pp] == left_char:
			left_ans += 1
			pp += 1
		elif s[qq] == left_char:
			left_ans += 1
			qq -= 1
		else:
			left_ans = 992233
			break
	right_ans = 0
	right_char = s[q]
	pp = p
	qq = q
	while pp < qq:
		if s[pp] == s[qq]:
			pp += 1
			qq -= 1
		elif s[pp] == right_char:
			right_ans += 1
			pp += 1
		elif s[qq] == right_char:
			right_ans += 1
			qq -= 1
		else:
			right_ans = 992233
			break
	ans = min(left_ans, right_ans)
	if ans == 992233:
		print(-1)
	else:
		print(ans)


for u in range(int(input())):
	n = int(input())
	s = input()
	x = list(s)
	ans = 10 ** 9
	for i in range(26):
		l = 0
		r = n - 1
		temp = 0
		c = chr(i + ord('a'))
		while l <= r:
			if x[l] == x[r]:
				l += 1
				r -= 1
			elif x[l] == c:
				l += 1
				temp += 1
			elif x[r] == c:
				r -= 1
				temp += 1
			else:
				temp = 10 ** 9
				break
		ans = min(ans, temp)
	if ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	s = input()
	l = 0
	r = len(s) - 1
	while l <= r:
		if s[l] == s[r]:
			l += 1
			r -= 1
		else:
			ele1 = s[l]
			ele2 = s[r]
			break
	if l <= r:
		flag1 = True
		cnt1 = 0
		flag2 = True
		cnt2 = 0
		l = 0
		r = len(s) - 1
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			else:
				if s[l] != ele1 and s[r] != ele1:
					flag1 = False
					break
				if s[l] == ele1:
					l += 1
					cnt1 += 1
				if s[r] == ele1:
					r -= 1
					cnt1 += 1
		l = 0
		r = len(s) - 1
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			else:
				if s[l] != ele2 and s[r] != ele2:
					flag2 = False
					break
				if s[l] == ele2:
					l += 1
					cnt2 += 1
				if s[r] == ele2:
					r -= 1
					cnt2 += 1
		if flag1 == False and flag2 == False:
			print(-1)
		elif flag1 == True and flag2 == True:
			print(min(cnt1, cnt2))
		elif flag1 == True:
			print(cnt1)
		else:
			print(cnt2)
	else:
		print(0)


import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_left
from bisect import bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	tot = 0
	i = 0
	j = n - 1
	poss = 1
	while i < j:
		if s[i] == s[j]:
			pass
		else:
			poss1 = s[i]
			poss2 = s[j]
			res = 0
			i1 = i
			j1 = j
			f1 = 1
			f2 = 1
			while i < j:
				if s[i] == s[j]:
					i += 1
					j += -1
				elif s[i] == poss1:
					res += 1
					i += 1
				elif s[j] == poss1:
					res += 1
					j += -1
				else:
					f1 = 0
					break
			if f1:
				tot = res
			res = 0
			while i1 < j1:
				if s[i1] == s[j1]:
					i1 += 1
					j1 += -1
				elif s[i1] == poss2:
					res += 1
					i1 += 1
				elif s[j1] == poss2:
					res += 1
					j1 += -1
				else:
					f2 = 0
					break
			if f2:
				if tot == 0:
					tot = res
				else:
					tot = min(tot, res)
			if f1 == 0 and f2 == 0:
				poss = 0
		if not poss or tot > 0:
			break
		i += 1
		j += -1
	if not poss:
		print(-1)
	else:
		print(tot)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
	return int(input())

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
import itertools
from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from math import factorial, inf
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a, b, c):
	print(c, a, b, flush=True)
	n = I()
	return n

def linear_sieve(n):
	is_composite = [False] * n
	prime = []
	for i in range(2, n):
		if not is_composite[i]:
			prime.append(i)
		for j in prime:
			is_composite[i * j] = True
			if i % prime == 0:
				break
	return prime

def dfs(i, p, d):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
d = []
primes = []
prim = [0] * (10 ** 5 + 1)

def sieve(n):
	for i in range(n):
		d.append(i)
	for i in range(2, n):
		if d[i] == i:
			prim[i] = 1
			primes.append(i)
		j = 0
		while j < len(primes) and primes[j] <= d[i] and (primes[j] * i < n):
			d[i * primes[j]] = primes[j]
			j += 1

def primeFactors(n):
	factors = []
	while n != 1:
		factors.append(d[n])
		n //= d[n]
	return factors
mod = 1000000007
t = 1
t = I()
for _ in range(t):
	n = I()
	s = list(map(str, input().strip()))
	c = s.copy()
	c = set(c)
	ans = n + 1
	for i in c:
		(j, k) = (0, n - 1)
		cnt = 0
		while j < k:
			if s[j] == s[k]:
				j += 1
				k -= 1
			elif s[j] == i:
				j += 1
				cnt += 1
			elif s[k] == i:
				k -= 1
				cnt += 1
			else:
				cnt = n + 1
				break
		ans = min(cnt, ans)
	if ans == n + 1:
		print(-1)
	else:
		print(ans)


import decimal
import heapq
import math
import os
import sys
from array import array
from collections import Counter, deque
from io import BytesIO, IOBase
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ints_get():
	return map(int, input().strip().split())

def list_get():
	return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
	return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def ipn():
	return int(input())

def main():
	for _ in range(ipn()):
		n = ipn()
		s = [x for x in input()]
		c = Counter(s)
		out = 1000000000.0
		flag = 0
		for j in range(len(s)):
			if s[j] != s[len(s) - j - 1]:
				flag = 1
				break
		if flag == 0:
			out = 0
		for i in c:
			(p, q) = (0, len(s) - 1)
			flag = 0
			count = 0
			while p < q:
				if s[p] != s[q]:
					if s[p] == i:
						count += 1
						p += 1
					elif s[q] == i:
						count += 1
						q -= 1
					else:
						flag = 1
						break
				else:
					p += 1
					q -= 1
			if flag == 0:
				out = min(out, count)
		if out > 100000000.0:
			print(-1)
		else:
			print(out)
	return
main()


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left
mod = 998244353
mod = 1000000007

def solve1(c, s):
	i = 0
	j = len(s) - 1
	ans = 0
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif s[i] == c:
			ans += 1
			i += 1
		elif s[j] == c:
			ans += 1
			j -= 1
		else:
			return -1
	return ans

def solve(we):
	n = iin()
	s = input()
	z = []
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			x = solve1(s[i], s[i + 1:n - i])
			y = solve1(s[n - i - 1], s[i:n - i - 1])
			if x == y and x == -1:
				print(-1)
				return
			else:
				if x == -1:
					print(y + 1)
				elif y == -1:
					print(x + 1)
				else:
					print(min(x, y) + 1)
				return
	print(0)
qwe = 1
qwe = iin()
for _ in range(qwe):
	solve(_ + 1)


import sys
inp = sys.stdin.readline

def solve():
	n = int(inp())
	s = inp()
	a = 1e+18
	for i in range(26):
		c = chr(ord('a') + i)
		l = 0
		r = n - 1
		h = 0
		while l < r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == c:
				l += 1
				h += 1
			elif s[r] == c:
				r -= 1
				h += 1
			else:
				h = 1e+18
				break
		a = min(a, h)
	if a >= 1e+18:
		print(-1)
	else:
		print(a)

def main():
	for i in range(int(inp())):
		solve()
main()


testcase = int(input())
for test in range(0, testcase):
	n = int(input())
	a = input()
	if len(a) == 1:
		print(0)
	else:
		i = 0
		j = n - 1
		stop = False
		while a[i] == a[j] and stop == False:
			i += 1
			j -= 1
			if i >= j:
				print(0)
				stop = True
		if stop == False:
			temp1 = a[i]
			temp2 = a[j]
			i = 0
			j = n - 1
			count1 = 0
			stop1 = False
			while i < j and stop1 == False:
				if a[i] == a[j]:
					i += 1
					j -= 1
				else:
					if a[i] != temp1 and a[j] != temp1:
						stop1 = True
						count1 = 10 ** 9
					if a[i] == temp1:
						i += 1
						count1 += 1
					if a[j] == temp1:
						j -= 1
						count1 += 1
			i = 0
			j = n - 1
			count2 = 0
			stop2 = False
			while i < j and stop2 == False:
				if a[i] == a[j]:
					i += 1
					j -= 1
				else:
					if a[i] != temp2 and a[j] != temp2:
						stop2 = True
						count2 = 10 ** 9
					if a[i] == temp2:
						i += 1
						count2 += 1
					if a[j] == temp2:
						j -= 1
						count2 += 1
			if stop1 == True and stop2 == True:
				print(-1)
			else:
				print(min(count1, count2))


for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	ma = 10 ** 9
	mi = 0
	for i in range(26):
		ch = chr(97 + i)
		l = []
		ans = []
		for j in range(n):
			if s[j] != ch:
				l.append(j)
				ans.append(s[j])
		if ans[::-1] == ans:
			ma = 0
			if len(ans) >= 1:
				m = len(ans) + 2 * min(n - l[-1] - 1, l[0])
				for j in range(len(ans) - 1):
					m += min(l[j + 1] - l[j] - 1, l[len(ans) - j - 1] - l[len(ans) - j - 2] - 1)
				mi = max(mi, m)
	if ma == 10 ** 9:
		print(-1)
	else:
		print(n - mi)


def palincount(S, c):
	n = len(S)
	answer = 0
	i1 = 0
	i2 = n - 1
	while i1 < i2:
		if S[i1] != S[i2]:
			if S[i1] == c:
				answer += 1
				i1 += 1
			elif S[i2] == c:
				answer += 1
				i2 -= 1
			else:
				return [False, None]
		else:
			i1 += 1
			i2 -= 1
	return [True, answer]

def process(S):
	n = len(S)
	i = 0
	while i < n - 1 - i and S[i] == S[n - 1 - i]:
		i += 1
	if i >= n - 1 - i:
		return 0
	c1 = S[i]
	c2 = S[n - 1 - i]
	(t1, a1) = palincount(S, c1)
	(t2, a2) = palincount(S, c2)
	if not t1 and (not t2):
		return -1
	elif not t1:
		return a2
	elif not t2:
		return a1
	else:
		return min(a1, a2)
t = int(input())
for i in range(t):
	n = int(input())
	S = input()
	print(process(S))


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	res = n
	for i in range(26):
		l = 0
		r = n - 1
		cnt = 0
		while l <= r:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif ord(s[l]) == ord('a') + i:
				l += 1
				cnt += 1
			elif ord(s[r]) == ord('a') + i:
				r -= 1
				cnt += 1
			else:
				cnt = n
				break
		res = min(res, cnt)
	print(-1 if res == n else res)


import copy
import heapq
import itertools
import bisect
import collections
import math
import sys
import typing

def ni():
	return int(sys.stdin.buffer.readline())

def ns():
	return map(int, sys.stdin.buffer.readline().split())

def ns1():
	return map(lambda x: int(x) - 1, sys.stdin.buffer.readline().split())

def na():
	return list(map(int, sys.stdin.buffer.readline().split()))

def na1():
	return list(map(lambda x: int(x) - 1, sys.stdin.buffer.readline().split()))

def nall():
	return list(map(int, sys.stdin.buffer.read().split()))

def flush():
	return sys.stdout.flush()

def nic():
	return int(sys.stdin.readline())

def nsc():
	return map(int, sys.stdin.readline().split())

def nac():
	return list(map(int, sys.stdin.readline().split()))

def na1c():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
inf = 10 ** 20
mod = 10 ** 9 + 7

def solve():
	n = nic()
	s = input()
	a = [ord(s) - 97 for s in s]
	res = inf
	for i in range(26):
		(l, r) = (0, n - 1)
		tres = 0
		while r > l:
			if a[l] == a[r]:
				l += 1
				r -= 1
			elif a[l] == i:
				l += 1
				tres += 1
			elif a[r] == i:
				r -= 1
				tres += 1
			else:
				break
		else:
			res = min(res, tres)
	print(res if res != inf else -1)

def main():
	t = nic()
	for _ in range(t):
		solve()
main()


import math

def remove(s, c, i, j):
	count = 0
	while 0 <= i < j < len(s):
		if s[i] != s[j]:
			if s[i] == c:
				count += 1
				i += 1
			elif s[j] == c:
				count += 1
				j -= 1
			else:
				return -1
		else:
			i += 1
			j -= 1
	return count
for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n):
		if i >= math.floor(n / 2):
			print(0)
			break
		if s[i] != s[n - i - 1]:
			r1 = remove(s, s[i], i, n - i - 1)
			rn = remove(s, s[n - i - 1], i, n - i - 1)
			if r1 == -1 or rn == -1:
				print(r1 + rn + 1)
			else:
				print(min(r1, rn))
			break


from sys import *
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = input()
	if s == s[::-1]:
		stdout.write('0\n')
		continue
	if n == 2:
		print(1)
		continue
	ans = -1
	s1 = ''
	tmp1 = ''
	st = set()
	no = 0
	if s.count(s[0]) > 1:
		for i in range(n - 1, -1, -1):
			if s[i] != s[0]:
				st.add(s[i])
			else:
				break
		if len(st) == 1:
			c = 0
			pos = n - 1
			for i in range(n - 1, -1, -1):
				if s[i] == s[0]:
					break
				c += 1
				pos = i
			s1 = s[:pos]
			tmp1 = s[-1]
			i = 0
			j = pos - 1
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					no += 1
					break
			if no == 0:
				ans = c
		elif len(st) == 0:
			s1 = s
			tmp1 = ''
			tmp2 = ''
			i = 0
			j = len(s1) - 1
			c = 0
			ver = True
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				else:
					tmp1 = s1[i]
					tmp2 = s1[j]
					break
			i = 0
			j = len(s1) - 1
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					ver = False
					break
			if ver:
				if ans == -1:
					ans = c
				else:
					ans = min(ans, c)
			c = 0
			tmp1 = tmp2
			i = 0
			j = len(s1) - 1
			ver = True
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					ver = False
					break
			if ver:
				if ans == -1:
					ans = c
				else:
					ans = min(ans, c)
		else:
			no += 1
	s = s[::-1]
	s1 = ''
	tmp1 = ''
	st = set()
	if s.count(s[0]) > 1:
		for i in range(n - 1, -1, -1):
			if s[i] != s[0]:
				st.add(s[i])
			else:
				break
		if len(st) == 1:
			c = 0
			pos = n - 1
			for i in range(n - 1, -1, -1):
				if s[i] == s[0]:
					break
				c += 1
				pos = i
			s1 = s[:pos]
			tmp1 = s[-1]
			i = 0
			j = pos - 1
			ver = True
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					ver = False
					break
			if ver:
				if ans == -1:
					ans = c
				else:
					ans = min(ans, c)
		elif len(st) == 0:
			s1 = s
			tmp1 = ''
			tmp2 = ''
			i = 0
			j = len(s1) - 1
			c = 0
			ver = True
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				else:
					tmp1 = s1[i]
					tmp2 = s1[j]
					break
			i = 0
			j = len(s1) - 1
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					ver = False
					break
			if ver:
				if ans == -1:
					ans = c
				else:
					ans = min(ans, c)
			c = 0
			tmp1 = tmp2
			ver = True
			i = 0
			j = len(s1) - 1
			while i <= j:
				if s1[i] == s1[j]:
					i += 1
					j -= 1
				elif s1[i] == tmp1:
					i += 1
					c += 1
				elif s1[j] == tmp1:
					j -= 1
					c += 1
				else:
					no += 1
					ver = False
					break
			if ver:
				if ans == -1:
					ans = c
				else:
					ans = min(ans, c)
		else:
			no += 1
	stdout.write(str(ans) + '\n')


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	strev = st[::-1]
	ans = -1
	if st == strev:
		ans = 0
	else:
		b = set(st)
		b1 = set()
		for el in b:
			st1 = st.replace(el, '')
			strev1 = strev.replace(el, '')
			if st1 == strev1:
				b1.add(el)
		mn = 100001
		for el in b1:
			k = 0
			strev = st[::-1]
			i = 0
			j = 0
			st2 = ''
			while i < len(st) and j < len(strev):
				if st[i] == strev[j]:
					st2 = st2 + st[i]
					i += 1
					j += 1
				elif st[i] == el:
					i += 1
				elif strev[j] == el:
					j += 1
			k = n - len(st2)
			if k < mn:
				mn = k
		if mn < 100001:
			ans = mn
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	input_s = str(input())
	s = list(input_s)
	while n >= 2 and s[0] == s[n - 1]:
		del s[n - 1]
		del s[0]
		n -= 2
	s_new = []
	n_new = n
	for k in range(n):
		s_new.append(s[k])
	if n <= 1:
		erased = 0
	else:
		del_counter1 = 1
		del_counter2 = 1
		erased_el1 = s[0]
		erased_el2 = s[n - 1]
		del s[0]
		n -= 1
		while n >= 2 and del_counter1 != 999999:
			if s[0] == s[n - 1]:
				del s[n - 1]
				del s[0]
				n -= 2
			elif s[0] == erased_el1:
				del_counter1 += 1
				del s[0]
				n -= 1
			elif s[n - 1] == erased_el1:
				del_counter1 += 1
				del s[n - 1]
				n -= 1
			else:
				del_counter1 = 999999
		del s_new[n_new - 1]
		n_new -= 1
		while n_new >= 2 and del_counter2 != 999999:
			if s_new[0] == s_new[n_new - 1]:
				del s_new[n_new - 1]
				del s_new[0]
				n_new -= 2
			elif s_new[0] == erased_el2:
				del_counter2 += 1
				del s_new[0]
				n_new -= 1
			elif s_new[n_new - 1] == erased_el2:
				del_counter2 += 1
				del s_new[n_new - 1]
				n_new -= 1
			else:
				del_counter2 = 999999
		if del_counter1 == 999999 and del_counter2 == 999999:
			erased = -1
		else:
			erased = min(del_counter1, del_counter2)
	print(erased)


import os, sys, math
from io import BytesIO, IOBase
t = int(input())
for test in range(t):
	n = int(input())
	p = input()
	res = 10 ** 9
	pal = False
	for i in range(97, 123):
		c = chr(i)
		right = n - 1
		left = 0
		ans = 0
		while right > left:
			if p[right] == p[left]:
				right -= 1
				left += 1
			elif p[right] == c:
				right -= 1
				ans += 1
			elif p[left] == c:
				left += 1
				ans += 1
			else:
				ans = -1
				break
		if ans != -1:
			pal = True
			res = min(res, ans)
	if not pal:
		res = -1
	print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')


for tc in range(int(input())):
	n = int(input())
	s = input()
	candidate = 'abcdefghijklmnopqrstuvwxyz'
	score = 10 ** 6
	for c in candidate:
		isPalin = True
		erase = 0
		lptr = 0
		rptr = n - 1
		while lptr < rptr:
			left = s[lptr]
			right = s[rptr]
			if left != right:
				if left != c and right != c:
					isPalin = False
					break
				erase += 1
				if left == c:
					lptr += 1
				else:
					rptr -= 1
			else:
				lptr += 1
				rptr -= 1
		if isPalin:
			score = min(score, erase)
	if score == 10 ** 6:
		print(-1)
	else:
		print(score)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	chars = set(list(s))
	ans = float('inf')
	for c in chars:
		(f, b) = (0, n - 1)
		pal = True
		cnt = 0
		while f < b:
			if s[f] == s[b]:
				f += 1
				b -= 1
			else:
				cnt += 1
				if s[f] == c:
					f += 1
				elif s[b] == c:
					b -= 1
				else:
					pal = False
					break
		if pal:
			ans = min(ans, cnt)
	return ans if ans < float('inf') else -1
	return
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip('\n')
	li = list(set(s))
	ans = []
	for ele in li:
		(i, j) = (0, n - 1)
		(c, t) = (0, 0)
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == ele:
				c += 1
				i += 1
			elif s[j] == ele:
				c += 1
				j -= 1
			else:
				t = 1
				break
		if t == 0:
			ans.append(c)
	if len(ans) == 0:
		print(-1)
	else:
		print(min(ans))


t = int(input())
while t:
	n = int(input())
	s = input()
	d = {x: 1 for x in s}.keys()
	ans = n + 1
	for c in d:
		(i, j, cnt, flag) = (0, n - 1, 0, True)
		while i < j:
			if s[i] != s[j]:
				if s[i] == c:
					i += 1
				elif s[j] == c:
					j -= 1
				else:
					flag = False
					break
				cnt += 1
			else:
				i += 1
				j -= 1
		if flag:
			ans = min(ans, cnt)
	if ans == n + 1:
		print(-1)
	else:
		print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	minn = float('inf')
	for char in 'abcdefghijklmnopqrstuvwxyz':
		count = 0
		i = 0
		j = len(s) - 1
		found = True
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			elif s[i] == char:
				count += 1
				i += 1
			elif s[j] == char:
				count += 1
				j -= 1
			else:
				found = False
				break
		if found:
			minn = min(minn, count)
	if minn != float('inf'):
		print(minn)
	else:
		print(-1)


import bisect
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def __gcd(a, b):
	return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
	return a * b / __gcd(a, b)

def __fact(n):
	return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
	mex = 0
	a.sort()
	for x in a:
		if x <= mex:
			mex += 1
		else:
			break
	return mex

def __dist(x1, y1, x2, y2):
	return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
	isprime = [True for i in range(n + 1)]
	primes = []
	for i in range(2, n + 1):
		if isprime[i]:
			for j in range(i * i, n + 1, i):
				isprime[j] = False
	for i in range(2, n + 1):
		if isprime[i]:
			primes.append(i)
	return primes

def __cntprimediv(n):
	ret = 0
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			n //= i
			ret += 1
		i += 1
	if n > 1:
		ret += 1
	return ret

def __primefactors(n):
	ret = []
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret

def __sumdigit(n):
	ret = 0
	while n > 0:
		ret += n % 10
		n //= 10
	return ret

def solve(t):
	n = int(input())
	s = input()
	ans = n
	for c in range(26):
		l = 0
		sz = 10
		r = n - 1
		ok = True
		while r > l:
			while r > l and ord(s[l]) - ord('a') == c:
				l += 1
			while r > l and ord(s[r]) - ord('a') == c:
				r -= 1
			if r > l and s[l] != s[r]:
				ok = False
				break
			else:
				l += 1
				r -= 1
		if not ok:
			continue
		l = 0
		r = n - 1
		tmp = n
		while r > l:
			while r > l and s[l] == s[r]:
				tmp -= 2
				l += 1
				r -= 1
			while r > l and s[l] != s[r]:
				if ord(s[l]) - ord('a') == c:
					l += 1
				elif ord(s[r]) - ord('a') == c:
					r -= 1
		if l == r:
			tmp -= 1
		if ans > tmp:
			ans = tmp
	if ans == n:
		ans = -1
	print(ans)
t = 1
t = int(input())
for i in range(t):
	solve(i + 1)


import sys, os, io
import math
import bisect
t = int(input())
for a0 in range(t):
	n = int(input())
	s = input()
	st = 0
	end = n - 1
	while st < end and s[st] == s[end]:
		st += 1
		end -= 1
	if st >= end:
		print(0)
		continue
	w = [s[st], s[end]]
	chk = w[0]
	m = 0
	f1 = 0
	st1 = st
	end1 = end
	st2 = st
	end2 = end
	while st1 < end1:
		if s[st1] == s[end1]:
			st1 += 1
			end1 -= 1
		elif s[st1] == chk:
			st1 += 1
			m += 1
		elif s[end1] == chk:
			end1 -= 1
			m += 1
		else:
			f1 = 1
			break
	chk = w[1]
	m1 = 0
	f2 = 0
	while st2 < end2:
		if s[st2] == s[end2]:
			st2 += 1
			end2 -= 1
		elif s[st2] == chk:
			st2 += 1
			m1 += 1
		elif s[end2] == chk:
			end2 -= 1
			m1 += 1
		else:
			f2 = 1
			break
	if f1 == 1 and f2 == 1:
		print(-1)
	elif f1 == 1:
		print(m1)
	elif f2 == 1:
		print(m)
	else:
		print(min(m1, m))


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = [0] * 26
	ans = [0] * 26
	for i in range(26):
		dig = chr(i + 97)
		r = n - 1
		l = 0
		while r >= l:
			if s[l] == s[r]:
				l += 1
				r -= 1
			elif s[l] == dig:
				l += 1
				a[i] += 1
			elif s[r] == dig:
				r -= 1
				a[i] += 1
			else:
				a[i] = 10 ** 6
				break
	ans = min(a)
	if ans == 10 ** 6:
		print(-1)
	else:
		print(min(a))


ans = []
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	cur_ans = n + 1
	for o in range(26):
		if cur_ans == 0:
			break
		let = chr(ord('a') + o)
		t = []
		ind = []
		d = []
		for i in range(n):
			if s[i] != let:
				t.append(s[i])
				d.append(i)
			else:
				ind.append(i)
		for i in range(len(t) // 2):
			if t[i] != t[-i - 1]:
				break
		else:
			cur = len(ind)
			j = len(ind) - 1
			i = 0
			if len(d) == 0 or len(ind) == 0 or ind[i] > d[-1] or (ind[j] < d[0]):
				cur_ans = min(cur_ans, cur)
				continue
			L = R = 0
			for k in range(len(d)):
				if d[k] > ind[i]:
					L = k
					break
			for k in range(len(d)):
				if d[-k - 1] < ind[j]:
					R = k
					break
			while True:
				if i > j:
					break
				while L > R:
					j -= 1
					if j == -1:
						break
					for k in range(R, len(d)):
						if d[-k - 1] < ind[j]:
							R = k
							break
					else:
						R = len(d)
				if j == -1:
					break
				if L == R:
					if i == j:
						cur -= 1
					elif i < j:
						cur -= 2
					j -= 1
					if j == -1:
						break
					for k in range(R, len(d)):
						if d[-k - 1] < ind[j]:
							R = k
							break
					else:
						R = len(d)
				i += 1
				if i == len(ind):
					break
				for k in range(L, len(d)):
					if d[k] > ind[i]:
						L = k
						break
				else:
					L = len(d)
			cur_ans = min(cur_ans, cur)
	if cur_ans == n + 1:
		ans.append(-1)
	else:
		ans.append(cur_ans)
print('\n'.join(map(str, ans)))


from sys import stdin, stdout, setrecursionlimit
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
from heapq import *
mod = 10 ** 9 + 7
inf = 1 << 60
for _ in range(it()):
	n = it()
	a = list(input().strip())
	i = 0
	j = n - 1
	ele = None
	ans = 0
	count = 0
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		elif ele:
			if ele == a[j]:
				j -= 1
				count += 1
			elif ele == a[i]:
				i += 1
				count += 1
			else:
				ans = -1
				break
		else:
			ele = a[j]
			j -= 1
			count += 1
	ans1 = ans
	count1 = count
	i = 0
	j = n - 1
	ele = None
	ans = 0
	count = 0
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		elif ele:
			if ele == a[j]:
				j -= 1
				count += 1
			elif ele == a[i]:
				i += 1
				count += 1
			else:
				ans = -1
				break
		else:
			ele = a[i]
			i += 1
			count += 1
	if ans == -1 and ans1 == -1:
		print(-1)
	elif ans != -1 and ans1 != -1:
		print(min(count, count1))
	elif ans != -1:
		print(count)
	else:
		print(count1)


from os import environ
import sys
import math
if environ.get('hardik'):
	sys.stdin = open('../input.txt', 'r')
	sys.stdout = open('../output.txt', 'w')
input = sys.stdin.readline
print = sys.stdout.write
mod = 10 ** 9 + 7

def I():
	return input().strip()

def II():
	return int(input())

def MI():
	return map(int, input().split())

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

def P(z=''):
	print(str(z) + '\n')

def LP(z=[]):
	for i in z:
		print(str(i) + ' ')
	print('\n')

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for _ in range(II()):
	n = II()
	s = I()
	ans = float('inf')
	arr = [ord(i) - 97 for i in s]
	for i in range(26):
		change = 0
		l = 0
		r = n - 1
		while True:
			if l >= r:
				break
			if arr[l] == arr[r]:
				l += 1
				r -= 1
			elif arr[l] == i:
				l += 1
				change += 1
			elif arr[r] == i:
				r -= 1
				change += 1
			else:
				change = float('inf')
				break
		ans = min(ans, change)
	if ans == float('inf'):
		P(-1)
	else:
		P(ans)


import sys
from collections import Counter
import math
import bisect
import heapq
from itertools import combinations
from itertools import accumulate
from collections import defaultdict
from collections import deque
num_cases = int(sys.stdin.readline().strip())
for case in range(1, num_cases + 1):
	N = int(sys.stdin.readline().strip())
	S = list(str(sys.stdin.readline().strip()))
	type_alphabet = list(set(S))
	if len(type_alphabet) == 1:
		print(0)
	else:
		result = float('inf')
		for alphabet in type_alphabet:
			new_S = list(filter(lambda x: x != alphabet, S))
			break_signal = 0
			for i in range(len(new_S) // 2):
				if new_S[i] == new_S[len(new_S) - i - 1]:
					continue
				else:
					break_signal = 1
					break
			if break_signal == 0:
				index_basket = []
				semi_S = ['0'] + S + ['0']
				count = 0
				for (index, value) in enumerate(semi_S):
					if value != alphabet:
						index_basket.append(count)
						count = 0
					else:
						count += 1
				index_basket = index_basket[1:]
				real_count = 0
				for i in range(len(index_basket) // 2):
					must_erase = index_basket[i] + index_basket[len(index_basket) - 1 - i]
					real_count += must_erase - min(index_basket[i], index_basket[len(index_basket) - 1 - i]) * 2
				result = min(result, real_count)
		if result == float('inf'):
			print(-1)
		else:
			print(result)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cc = 97
	ans = 0
	while cc < 123:
		c = chr(cc)
		i = 0
		j = n - 1
		tmp = 0
		while i < j:
			if s[i] == s[j]:
				tmp += 2
				i += 1
				j -= 1
				continue
			if s[i] == c:
				i += 1
				continue
			if s[j] == c:
				j -= 1
				continue
			tmp = 0
			break
		if i == j:
			tmp += 1
		ans = max(ans, tmp)
		cc += 1
	if ans == 0:
		print(-1)
	else:
		print(n - ans)


import sys
input = sys.stdin.readline

def cntSame(string, x):
	(s, e) = (0, len(string) - 1)
	cnt = 0
	while s <= e:
		if string[s] == string[e]:
			s += 1
			e -= 1
		elif string[s] == x:
			cnt += 1
			s += 1
		elif string[e] == x:
			cnt += 1
			e -= 1
		else:
			return -1
	return cnt
t = int(input())
for __ in range(t):
	n = int(input())
	string = input().rstrip()
	flag = 1
	cnt = int(1000000000.0)
	for x in 'abcdefghijklmnopqrstuvwxyz':
		s = string.replace(x, '')
		nnum = cntSame(string, x)
		if nnum != -1:
			flag = 0
			cnt = min(cnt, nnum)
	print(-1 if flag else cnt)


import collections as cc
import bisect as bi
import itertools
import math as mt
import sys
q = lambda x: print('?', *x, flush=True)
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n,) = I()
	s = list(input().strip())
	i = 0
	j = 0

	def ch(string, r):
		i = 0
		j = len(string) - 1
		tf = 1
		rm = 0
		while i < j:
			if string[i] == string[j]:
				i += 1
				j -= 1
			elif string[i] == r:
				i += 1
				rm += 1
			elif string[j] == r:
				j -= 1
				rm += 1
			else:
				tf = 0
				break
		return rm if tf else -1
	temp = []
	i = 0
	j = len(s) - 1
	tempst = ''
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			temp.append(s[i])
			temp.append(s[j])
			tempst = s[i:j + 1]
			break
	ans = []
	for i in temp:
		now = ch(tempst, i)
		ans.append(now)
	if ans:
		if ans.count(-1) == 2:
			print(-1)
		elif ans.count(-1) == 0:
			print(min(ans))
		else:
			print(max(ans))
	else:
		print(0)