A. Палиндромные индексы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n$$$, которая является палиндромом.

Вы должны посчитать количество индексов $$$i$$$ $$$(1 \le i \le n)$$$ таких, что строка после удаления $$$s_i$$$ из $$$s$$$ остается палиндромом.

Например, рассмотрим $$$s$$$ = «aba»

  1. Если мы удалим $$$s_1$$$ из $$$s$$$, то строка станет «ba», что не является палиндромом.
  2. Если мы удалим $$$s_2$$$ из $$$s$$$, строка станет «aa», что является палиндромом.
  3. Если мы удалим $$$s_3$$$ из $$$s$$$, строка станет «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_i$$$ из $$$s$$$ остается палиндромом.

Пример
Входные данные
3
3
aba
8
acaaaaca
2
dd
Выходные данные
1
4
2
Примечание

Первый набора входных данных описан в условии.

Во втором наборе входных данных индексы $$$i$$$, которые приводят к палиндрому после удаления $$$s_i$$$, это $$$3, 4, 5, 6$$$. Следовательно, ответ  — $$$4$$$.

В третьем наборе входных данных удаление любого из индексов приводит к «d», что является палиндромом. Следовательно, ответ равен $$$2$$$.