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