Description

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

小明希望把S变成回文串，所以他打算采取删除S的若干字母，使得剩下的字母构成的字符串是回文串，

但是删除操作必须同时满足如下两个条件：

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

2、小明希望删除的字母的数量最少。

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

Input Format

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1<=G<=100.

每组测试数据格式如下：

第1行，一个整数n,  1<=n<=100000.

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

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

Output Format

5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky

2
-1
0
3
2

Hint

提示

第一组测试数据： 

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

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

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

Source