Строка s длины n называется k-палиндромом, если она сама является палиндромом, а ее префикс и суффикс длины 
являются (k - 1)-палиндромами. 0-палиндромом является любая строка (даже пустая).
Назовем палиндромностью строки s такое максимальное число k, для которого s является k-палиндромом. Например, палиндромность строки «abaaba» равна 3.
Дана строка. Ваша задача — найти сумму палиндромностей всех ее префиксов.
Выходные данные
Выведите единственное число — сумму палиндромностей всех префиксов данной строки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
a2A
|
1
|
|
2
|
abacaba
|
6
|