给你一个长度为 $$$n$$$ 的回文字符串 $$$s$$$。
您必须计算索引 $$$i$$$ $$$(1 \le i \le n)$$$ 的数量,以便从 $$$s$$$ 中删除 $$$s_i$$$ 后的字符串仍然是回文。
例如,考虑 $$$s$$$ = "aba"
1. 如果我们从$$$s$$$中删除$$$s_1$$$,则字符串变为“ba”,这不是回文。
2. 如果我们从 $$$s$$$ 中删除 $$$s_2$$$,则字符串变为“aa”,这是一个回文。
3. 如果我们从 $$$s$$$ 中删除 $$$s_3$$$,则字符串变为“ab”,这不是回文。
回文是向后读与向前读相同的字符串。例如,“abba”、“a”、“fef”是回文,而“codeforces”、“acd”、“xy”则不是。
输入
输入由多个测试用例组成。输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个由小写英文字母组成的字符串$$$s$$$。保证 $$$s$$$ 是回文。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 索引 $$$i$$$ $$$(1 \le i \le n)$$$ 的数量,这样从 $$$s$$$ 中删除 $$$s_i$$$ 后的字符串仍然是回文。
示例
输入 #1
3 3 aba 8 acaaaaca 2 dd
输出 #1
1 4 2
注意
语句中描述了第一个测试用例。
在第二个测试用例中,删除 $$$s_i$$$ 后产生回文的索引 $$$i$$$ 为 $$$3, 4, 5, 6$$$。因此答案是$$$4$$$。
在第三个测试用例中,删除任何索引都会产生回文“d”。因此答案是$$$2$$$。