卡帕奶奶决定织一条围巾,并请谢尔爷爷为它制作一个图案,图案是一串由小写英文字母组成的字符串。谢尔爷爷写了一个长度为 $$$n$$$ 的字符串 $$$s$$$。
卡帕奶奶想织一条漂亮的围巾,在她看来,漂亮的围巾只能用回文串来织。她想改变谢尔爷爷写的模式,但为了避免冒犯他,她会选择一个小写英文字母,并删除字符串 $$$s$$$ 中出现的一些(由她选择,可能没有或全部)该字母。
她还希望最大限度地减少图案中擦除符号的数量。请帮助她,找到她可以擦除的最少符号数,以使字符串 $$$s$$$ 成为回文,或者告诉她这是不可能的。请注意,她只能擦除等于她选择的一个字母的符号。
如果一个字符串从左到右和从右到左都相同,则该字符串是回文。例如,字符串“kek”、“abacaba”、“r”和“papicipap”是回文,而字符串“abb”和“iq”则不是。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。接下来的 $$$2 \cdot t$$$ 行包含测试用例的描述。每个测试用例的描述由两行组成。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串的长度。
每个测试用例的第二行包含由 $$$n$$$ 小写英文字母组成的字符串 $$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果可能,则打印使字符串成为回文所需的最小擦除符号数,如果不可能,则打印 $$$-1$$$。
示例
输入 #1
5 8 abcaacab 6 xyzxyz 4 abba 8 rprarlap 10 khyyhhyhky
输出 #1
2 -1 0 3 2
注意
在第一个测试用例中,您可以选择一个字母“a”并删除它的第一次和最后一次出现,您将得到一个字符串“bcaacb”,这是一个回文。您还可以选择字母“b”并删除所有出现的地方,您将得到一个字符串“acaaca”,它也是一个回文。
在第二个测试用例中,可以证明不可能选择一个字母并删除它的一些出现来获得回文。
在第三个测试用例中,您不必删除任何符号,因为该字符串已经是回文。