D. Палиндромность
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Строка s длины n называется k-палиндромом, если она сама является палиндромом, а ее префикс и суффикс длины являются (k - 1)-палиндромами. 0-палиндромом является любая строка (даже пустая).

Назовем палиндромностью строки s такое максимальное число k, для которого s является k-палиндромом. Например, палиндромность строки «abaaba» равна 3.

Дана строка. Ваша задача — найти сумму палиндромностей всех ее префиксов.

Входные данные

В первой строке входных данных записана непустая строка, состоящая из букв латинского алфавита и цифр. Длина строки не превосходит 5·106. Регистр букв следует различать.

Выходные данные

Выведите единственное число — сумму палиндромностей всех префиксов данной строки.

Примеры
Входные данные
a2A
Выходные данные
1
Входные данные
abacaba
Выходные данные
6