У Азизхана есть строка S. Его интересует сколько есть подстрок четной длины у строки S, которые являются палиндромами. Одинаковые подстроки начинающие с разных позиций считаются разными.
Формат входных данных
Единственная строка входного файла содержит одну строку S состоящее из строчных букв английского алфавита (1 <= длина S <= 100000).<br>