J1 习题-4 奶奶的魔法围巾

题目描述

在一个寒冷的冬日，住在魔法小镇的卡帕奶奶正在为她最疼爱的孙子编织一条特殊的围巾。这条围巾不仅要保暖，还需要蕴含魔法的力量。

卡帕奶奶用魔法丝线编织出了一串字符 $s$，每个字符代表围巾上的一种独特花纹。为了激活围巾的魔法，这些花纹必须形成回文图案（从左往右看和从右往左看是一样的）。

奶奶发现她可以通过以下方法调整围巾的花纹： $1$、选择一种特定的花纹（一个字母） $2$、移除这种花纹中的任意数量（可以是 $0$ 个或多个） $3$、使得剩余的花纹形成回文图案

由于每移除一个花纹都会消耗一些魔法能量，奶奶希望用最少的魔法能量（即移除最少的花纹）来完成这个任务。

输入格式

共 $2 \times t +1$ 行：

第一行输入一个正整数 $t$ ，表示奶奶准备制作的围巾数量。

每条围巾，共两行数据： 第一行一个正整数 $n$，表示字符串长度； 第二行一个长度为 $n$ 的字符串 $s$ 。

输出格式

每条围巾输出一行一个整数，如果存在方案，输出最少删除的花纹数量，如果不存在，输出 -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

数据范围

对于 $100\%$ 的数据：$1\le t\le100,1\le n\le10^5,1\le\sum n\le2\times10^5$ 。