You are given a string S of length N.

Your task is to delete a [subsequence] of maximum length from the string, such that, after concatenating the remaining parts of the string, it becomes a [palindrome] of length greater than 1.

If this is possible, print the maximum length of the subsequence that can be deleted. Otherwise, print -1.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of 2 lines of input:
- The first line consists the a single integer N - the length of string S.
- The second line contains string S, consisting of lowercase english alphabets.

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

For each test case, if it is possible to delete a subsequence under the given conditions, print a single integer, denoting the maximum length of the subsequence that can be deleted. Otherwise, print -1.

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

$1 ≤ T ≤ 2500$
$3 ≤ N ≤ 100$
$S$ consists of lowercase english alphabets.

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
3
6
babkhj
3 
abc 
4 
qtoo
----- Sample Output 1 ------ 
4
-1
2 

----- explanation 1 ------ 
Test case $1$: Possible ways to delete a subsequence are:
- Delete subsequence khj to get palindrome bab. 
- Delete subsequence akhj to get palindrome bb.

The subsequence having maximum length that can be deleted is akhj, having length $4$.

Test case $2$: We cannot delete any subsequence under the given conditions.

Test case $3$: We can delete the subsequence qt to obtain the string oo, which is a palindrome. This is the only subsequence that can be deleted and it has length $2$.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = set(s)
	if len(s1) == len(s):
		print(-1)
	else:
		print(len(s) - 2)


for i in range(int(input())):
	l = int(input())
	s = list(input())
	for j in range(l):
		if s[j] in s[j + 1:]:
			print(l - 2)
			break
	else:
		print(-1)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	d = {}
	for i in range(n):
		if s[i] in d.keys():
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	flag = False
	for (k, v) in d.items():
		if v >= 2:
			flag = True
	if flag:
		print(n - 2)
	else:
		print(-1)


def f():
	n = int(input())
	rt = input().strip()
	abc = 'abcdefghijklmnopqrstuvwxyz'
	pl = [0] * len(abc)
	for i in rt:
		pl[abc.index(i)] += 1
	fnd = []
	for i in pl:
		if i > 0:
			fnd.append(i)
	if max(fnd) >= 2:
		return len(rt) - 2
	return -1
t = int(input())
for test in range(t):
	print(f())


for i in range(int(input())):
	N = int(input())
	S = input()
	c = 0
	for j in S:
		if S.count(j) >= 2:
			c += 1
			print(N - 2)
			break
	if c == 0:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in s:
		cnt = s.count(i)
		if cnt >= 2:
			print(n - 2)
			break
	else:
		print(-1)


for i in range(int(input())):
	t = int(input())
	s = list(input())
	s1 = list(set(s))
	if len(s) == len(s1):
		print('-1')
	else:
		print(t - 2)


for i in range(int(input())):
	n = int(input())
	string = input()
	count = 0
	for i in string:
		count = string.count(i)
		if count >= 2:
			print(n - 2)
			break
	else:
		print('-1')


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	s1 = set(string)
	if len(string) == len(s1):
		print(-1)
	else:
		print(len(string) - 2)


for i in range(int(input())):
	l = int(input())
	s = input()
	k = set(s)
	if len(s) == len(k):
		print(-1)
	else:
		print(len(s) - 2)


def fun(s):
	fc = [0] * 28
	for i in s:
		t = ord(i) % 96
		fc[t] += 1
	m = max(fc)
	if m == 1:
		return -1
	else:
		return len(s) - 2
for i in range(int(input())):
	n = int(input())
	s = input()[0:n]
	print(fun(s))


for i in range(int(input())):
	n = int(input())
	x = input()
	for i in x:
		c = x.count(i)
		if c >= 2:
			print(n - 2)
			break
	else:
		print(-1)


for i in range(int(input())):
	k = int(input())
	l = input()
	l = list(l)
	h = set(l)
	h = list(h)
	if len(l) == len(h):
		print('-1')
	else:
		print(len(l) - 2)


n = int(input())
for i in range(n):
	n1 = int(input())
	s = input()
	s1 = set(s)
	if len(s) == len(s1):
		print(-1)
	else:
		print(n1 - 2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	dup_ = set(s)
	if len(dup_) == len(s):
		print('-1')
	else:
		print(len(s) - 2)


for i in range(int(input())):
	n = int(input())
	arr = list(input())
	a = set(arr)
	if len(arr) == len(set(arr)):
		print(-1)
	else:
		print(n - 2)


from statistics import mode
for t in range(int(input())):
	n = int(input())
	a = list(map(str, input().strip()))
	r = mode(a)
	t = a.count(r)
	if t > 1:
		print(len(a) - 2)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	f = 1
	for i in s:
		if s.count(i) > 1:
			print(n - 2)
			f = 1
			break
		else:
			f = 0
	if f == 0:
		print(-1)


s = int(input())
for i in range(s):
	a = int(input())
	b = input()
	b_new = set(b)
	if len(b) == len(b_new):
		print(-1)
	else:
		print(len(b) - 2)


for i in range(int(input())):
	N = int(input())
	S = input()
	dis_str = set(S)
	if len(S) == len(dis_str):
		print(-1)
	else:
		print(len(S) - 2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 0
	for j in range(n):
		if count == 0:
			for k in range(n):
				if s[j] == s[k] and j != k:
					count = 1
					print(n - 2)
					break
	if count == 0:
		print('-1')


for r in range(int(input())):
	n = int(input())
	s = input()
	frequency = {}
	f = 0
	for item in s:
		if item in frequency:
			frequency[item] += 1
			print(len(s) - 2)
			f = 1
			break
		else:
			frequency[item] = 1
	if f != 1:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	d = {}
	s = input()
	for i in s:
		d.setdefault(i, 0)
		d[i] += 1
	p = 0
	for (k, v) in d.items():
		if v >= 2:
			p = 2
			break
	if p == 0:
		print(-1)
	else:
		print(len(s) - p)


for i in range(int(input())):
	n = int(input())
	s = str(input())
	l = []
	l[:0] = s
	if len(set(l)) == len(l):
		print(-1)
	else:
		print(len(s) - 2)


for t in range(int(input())):
	n = int(input())
	s = input()
	x = len(set(s))
	if len(s) == x:
		print(-1)
	else:
		print(len(s) - 2)


for T in range(int(input())):
	n = int(input())
	s = input()
	for x in s:
		if s.count(x) > 1:
			print(n - 2)
			break
		elif x == s[-1]:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	m = {}
	for c in s:
		m[c] = m.get(c, 0) + 1
	ans = -1
	for k in m:
		if m[k] > 1:
			ans = len(s) - 2
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = []
	flag = 1
	for i in range(n):
		if s[i] in k:
			continue
		else:
			k.append(s[i])
	for i in k:
		if s.count(i) >= 2:
			flag = 0
			break
	print(n - 2 if flag == 0 else -1)


import math
for t in range(int(input())):
	n = int(input())
	s = input()
	s1 = set(s)
	if len(s) == len(s1):
		print('-1')
	else:
		print(len(s) - 2)


for _ in range(int(input())):
	x = int(input())
	s = input()
	p = set(s)
	if len(p) == len(s):
		print(-1)
	else:
		print(len(s) - 2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ct = 0
	for i in s:
		if s.count(i) > 1:
			ct += 1
	if ct >= 1:
		print(n - 2)
	else:
		print('-1')


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	b = 0
	for a in s:
		c = 0
		for j in range(n):
			if a == s[j]:
				c += 1
		if c >= 2:
			b += 1
	if b >= 1:
		print(n - 2)
	else:
		print('-1')


for _ in range(0, int(input())):
	s = int(input())
	a = input()
	a1 = set(a)
	if len(a) == len(a1):
		print(-1)
	else:
		print(len(a) - 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = set(s)
	if len(a) == len(s):
		print(-1)
	else:
		print(len(s) - 2)


for _ in range(int(input())):
	x = int(input())
	y = input()
	yt = set(y)
	t = 0
	for i in yt:
		if y.count(i) > 1:
			print(x - 2)
			t = 1
			break
	if t == 0:
		print('-1')


for _ in range(int(input())):
	x = int(input())
	y = input()
	yt = ''
	for i in y:
		if i not in yt:
			yt += i
	if y == yt:
		print('-1')
	else:
		print(x - 2)


def ans(n, str1):
	for j in range(n):
		for k in range(j + 1, n):
			if str1[k] == str1[j]:
				return n - 2
	else:
		return -1
for i in range(int(input())):
	n = int(input())
	str1 = input()
	print(ans(n, str1))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = ''.join(sorted(s))
	b = True
	for j in range(len(c) - 1):
		if c[j] == c[j + 1]:
			print(n - 2)
			b = False
			break
	if b:
		print(-1)


test_cases = int(input())
for i in range(test_cases):
	N = int(input())
	S = input()
	set_S = set(S)
	if len(S) == len(set_S):
		print(-1)
	else:
		print(len(S) - 2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	check = True
	for i in s:
		if s.count(i) >= 2:
			print(n - 2)
			check = False
			break
	if check == True:
		print(-1)


for i in range(int(input())):
	x = int(input())
	y = input()
	m = -1
	for j in y:
		o = y.count(j)
		if o > 1:
			m = 1
			break
	if m == 1:
		print(x - 2)
	else:
		print(-1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = list(Counter(s).values())
	i = 0
	while i < len(c):
		if c[i] == 1:
			i += 1
		else:
			print(len(s) - 2)
			break
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = sorted(s)
	flag = 0
	for i in s:
		if s.count(i) >= 2:
			flag = 1
			break
	if flag == 1:
		print(n - 2)
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	s1 = set(s)
	if len(s1) == len(s):
		print(-1)
	else:
		print(len(s) - 2)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	dic = {}
	flag = False
	for i in s:
		dic[i] = dic.get(i, 0) + 1
		if dic[i] == 2:
			print(n - 2)
			flag = True
			break
	if flag == False:
		print(-1)


t = int(input())
for _ in range(t):
	a = int(input())
	s = input()
	s1 = set(s)
	if len(s) == len(s1):
		print('-1')
	else:
		print(len(s) - 2)


n = int(input())
for i in range(0, n):
	m = int(input())
	s = input()
	s1 = set(s)
	if len(s1) == len(s):
		print(-1)
	else:
		print(len(s) - 2)


for i in range(int(input())):
	n = int(input())
	x = input()
	for i in x:
		res = x.count(i)
		if res >= 2:
			flag = 1
			break
		else:
			flag = 0
	if flag == 1:
		print(n - 2)
	else:
		print('-1')