Вам дана строка \(s\) длины \(n\), которая является палиндромом.
Вы должны посчитать количество индексов \(i\) \((1 \le i \le n)\) таких, что строка после удаления \(s_i\) из \(s\) остается палиндромом.
Например, рассмотрим \(s\) = «aba»
- Если мы удалим \(s_1\) из \(s\), то строка станет «ba», что не является палиндромом.
- Если мы удалим \(s_2\) из \(s\), строка станет «aa», что является палиндромом.
- Если мы удалим \(s_3\) из \(s\), строка станет «ab», что не является палиндромом.
Палиндром — это строка, которая слева направо читается так же, как справа налево. Например, «abba», «a», «fef» являются палиндромами, а «codeforces», «acd», «xy» — нет.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество индексов \(i\) \((1 \le i \le n)\) таких, что строка после удаления \(s_i\) из \(s\) остается палиндромом.
Примечание
Первый набора входных данных описан в условии.
Во втором наборе входных данных индексы \(i\), которые приводят к палиндрому после удаления \(s_i\), это \(3, 4, 5, 6\). Следовательно, ответ — \(4\).
В третьем наборе входных данных удаление любого из индексов приводит к «d», что является палиндромом. Следовательно, ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
aba
8
acaaaaca
2
dd
|
1
4
2
|