CF1682A.Palindromic Indices

You are given a palindromic string $s$ of length $n$.

You have to count the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.

For example, consider $s$ = "aba"

1. If we remove $s_1$ from $s$, the string becomes "ba" which is not a palindrome.
2. If we remove $s_2$ from $s$, the string becomes "aa" which is a palindrome.
3. If we remove $s_3$ from $s$, the string becomes "ab" which is not a palindrome.

A palindrome is a string that reads the same backward as forward. For example, "abba", "a", "fef" are palindromes whereas "codeforces", "acd", "xy" are not.

给你一个长度为 $n$ 的回文字符串 $s$。

你需要统计满足如下条件的下标 $i$（$1 \le i \le n$）的个数：从 $s$ 中删除字符 $s_i$ 后，所得字符串仍是回文串。

例如，考虑 $s =$ "aba"：

1. 若删除 $s_1$，字符串变为 "ba"，不是回文串。
2. 若删除 $s_2$，字符串变为 "aa"，是回文串。
3. 若删除 $s_3$，字符串变为 "ab"，不是回文串。

回文串是指正读与反读都相同的字符串。例如，"abba"、"a"、"fef" 是回文串，而 "codeforces"、"acd"、"xy" 不是回文串。

The input consists of multiple test cases. The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^3)$ — the number of test cases. Description of the test cases follows.

The first line of each testcase contains a single integer $n$ $(2 \leq n \leq 10^5)$ — the length of string $s$.

The second line of each test case contains a string $s$ consisting of lowercase English letters. It is guaranteed that $s$ is a palindrome.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。输入的第一行包含一个整数 $t$ $(1 \leq t \leq 10^3)$，表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$，表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个由小写英文字母组成的字符串 $s$。保证 $s$ 是一个回文串。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the number of indices $i$ $(1 \le i \le n)$ such that the string after removing $s_i$ from $s$ still remains a palindrome.

对于每个测试用例，输出一个整数——满足条件的下标 $i$（$1 \le i \le n$）的个数，使得从字符串 $s$ 中删除字符 $s_i$ 后，剩余字符串仍为回文串。

The first test case is described in the statement.

In the second test case, the indices $i$ that result in palindrome after removing $s_i$ are $3, 4, 5, 6$. Hence the answer is $4$.

In the third test case, removal of any of the indices results in "d" which is a palindrome. Hence the answer is $2$.

第一个测试用例已在题目描述中给出。

在第二个测试用例中，删除字符 $s_i$ 后能得到回文串的下标 $i$ 为 $3, 4, 5, 6$。因此答案为 $4$。

在第三个测试用例中，删除任意一个下标对应的字符均得到字符串 "d"，而 "d" 是回文串。因此答案为 $2$。