给定一个字符串，你可以删除多个(可以是 $0$) 相同 的字符，这样操作之后，你能否得到一个回文串？如果能，求最小化删除的个数。

输入格式

多组数据。

每一组数据包含两行，分别为字符串的长度 $N$，以及一个仅由小写字母组成的字符串 $S$。

输出格式

对于每一组数据，输出一行。

如果不可能得到一个回文串，输出 $-1$。反之则输出最小操作次数。

样例输入

4
8
bilibili
3
qwq
9
daimayuan
7
xcpcxpc

样例输出

1
0
-1
2

解释：

在第一个例子中，删除开头的 b 得到 ilibili。

第二个例子中，qwq 本身已回文，不需要操作。

第三个例子中，可以看到 daimayuan 不能靠仅删除一种字符得到一个回文串。

数据规模

• $1 \le N \le 10^5$, 但保证 $\sum N \le 2 \times 10 ^ 5$