Рядок називається паліндромом, якщо він однаково читається як зліва направо, так і зправа наліво. Наприклад, "abba" - паліндром, а "omax" - ні. Для рядка α будемо позначати α[i..j] його підрядок довжини j - i + 1 з i-ої по j-ту позицію включно (позиції нумеруються з 1).

Для заданого рядка α довжини n знайдіть кількість q пар (i, j), 1 ≤ i < j ≤ n, таких що α[i..j] є паліндромом.

Вхідні дані

Рядок α довжини n (1 ≤ n ≤ 105), який складається з маленьких латинських літер.

Вихідні дані

Кількість шуканих пар q.