Подстрокой называется непрерывный и непустой подотрезок букв из данной строки, без изменения порядка.
Чётным палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево, и имеет чётную длину. Например, строки «zz», «abba», «abccba» являются чётными палиндромами, а строки «codeforces», «reality», «aba», «c» не являются.
Красивой строкой называется чётный палиндром или строка, которую можно разбить на несколько меньших чётных палиндромов.
Дана строка \(s\), состоящая из \(n\) строчных латинских букв. Подсчитайте количество красивых подстрок в \(s\).
Выходные данные
Для каждого набора входных данных выведите количество красивых подстрок.
Примечание
В первом наборе входных данных красивыми подстроками являются «abaaba», «baab», «aa».
В последнем наборе входных данных красивыми подстроками являются «aa» (подсчитано дважды), «abba», «bb», «bbaa», «abbaaa».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
|
3
0
1
0
14
6
|