Назовем строку $S$ почти палиндромом, если среди равенств вида $S_i = S_{|S| - i + 1}$ ровно одно неверно. Например, строки ab, abacada, abc являются почти палиндромами, а строки aa, abacaba, abcd – нет.

Вам дана строка, требуется найти количество подстрок почти палиндромов в ней.

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

Во входных данных записана непустая строка, состоящая из маленьких латинских символов. Ее длина не превосходит $10^5$.

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

Выведите единственное число – количество подстрок почти палиндромов.

Подзадачи