← 返回题目列表

Codeforces · 1682/A

A. 回文索引

中文机器翻译题面 查看原题

给你一个长度为 $$$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$$$。