← 返回比赛

已结束 GESP欢乐赛 #6

← 上一题下一题 →

A1453 | $围巾$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

$AC$ 狗准备织一条围巾，并请小 $A$ 设计一个图案，图案是由小写字母组成字符串，小 $A$ 写下了一个长度为 $n$ 的字符串 $s$。 $AC$ 狗想要一条漂亮的围巾，在它看来，漂亮的围巾的图案应该是回文的。于是，它想改变小 $A$ 设计的图案，但是为了避免冒犯小 $A$，它将选择一个小写的英文字母，并在 $s$ 中删除该字母（可能删除所有，也有可能删除部分）。 它还想尽量减少图案中被删除的字母的数量。请帮助它找出它可以删除的字母的最小数目，使 $s$ 变为回文串。注意，$AC$ 狗只能删除它选择的一个字母的符号。 请你帮助 $AC$ 狗解决这个问题。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)——表示测试用例的数目。 每个测试用例的第一行包含一个整数 $n$($1 \le n \le 10^5$)，即 $s$ 的长度。 每个测试用例的第二行包含字符串 $s$。

输出格式

对于每个测试用例，如果删除某个字母可以使 $s$ 回文，输出使 $s$ 变为回文所删除的字母的最小数目。否则，输出 -1 。

输入输出样例

输入 #1

5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky

输出 #1

C++ 编辑器

输入

输出