Паліндроми

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

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