题目描述

有一个长度为 n 的字符串 S ，它全部由小写英文字母构成。

小明希望把 S 变成回文串，所以他打算采取删除 S 的若干字母，使得剩下的字母构成的字符串是回文串，但是删除操作必须同时满足如下两个条件：

1. 只能删除同一种类型的字母，例如：只能删除字母 'a' , 不能既删除 'a' 又删除 'b' 。

2. 小明希望删除的字母的数量尽可能少。

问：小明至少删除多少个字母才能完成任务？如果不可能完成任务，输出 -1 。

输入格式

多组测试数据。

第一行，一个整数 G ，表示有 G 组测试数据 ( 1 <= G <= 100 );

每组测试数据格式如下：

第 1 行，一个整数 n ( 1 <= n <= 100000 )

第 2 行，一个字符串 S ，长度不超过 100000 。

数据保证：所有 G 组测试数据的 n 的总和不超过 200000 。

输出格式

共 G 行，每行一个整数。

样例

5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky

2
-1
0
3
2

样例解释

对字符串 "abcaacab" 的处理解释：

方案 1 : 你可以删除 'a' 这种类型的字母，删除 S 的第一个 'a' 和最后一个 'a' 。

方案 2 : 你可以删除 'b' 这种类型的字母，把 S 的所有 'b' 都删除。

不管是方案 1 还是方案 2 ，都是删除两个字母。