Remote Training on Programming

Назовём палиндромом строку длиной более одного символа, которая одинаково читается как справа налево, так и слева направо. Назовём суперпалиндромом строку, которая может быть представлена как конкатенация одного или более палиндромов. Дана строка S. Необходимо найти количество подстрок в S, которые являются суперпалиндромами.

Время тестирования: 2 секунды на один тест

В первой строке входного файла содержится S — последовательность от 1 до 1000 строчных латинских букв без пробелов.

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

Примеры

input	output
abc	0
abacdc	3