题目描述

给一个由小写字母组成的字符串 $s$ ，选择一个字母，删去这个字符串中任意个这个字母，使这个字符串变成回文的。如果存在多个答案，输出删除的字母个数最少的答案

输入格式

第一行输入一个正整数 $t$ ，表示数据组数。
对于每一组数据，第一行输入一个正整数 $n$ 表示字符串长度，第二行输入长度为 $n$ 的字符串 $s$
$1\le t\le100,1\le n\le10^5$

输出格式

对于每组数据输出一行一个整数，如果存在方案，输出最少删除的字母的个数，如果不存在，输出 $-1$

样例

5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky

2
-1
0
3
2

第一组数据，删除 $2$ 个 $a$ ，字符串变为 $bcaacb$ 。

第二组数据，方案不存在。

第三组数据，字符串本身就是回文的。

第四组数据，删除 $3$ 个 $r$ ，字符串变为 $palap$ 。

第五组数据，删除 $2$ 个 $y$ ，字符串变为 $khyhhyhk$