## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Palindromic Indices Codeforces Solution | Codeforces Problem Solution 2022

A. Palindromic Indices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

You have to count the number of indices $i$ $\left(1\le i\le n\right)$ 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.

Input

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

The first line of each testcase contains a single integer $n$ $\left(2\le n\le {10}^{5}\right)$  — 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}$.

Output

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