Polindromlar

Sətir palindrome adlanır, əgər onu soldan sağa və sağdan sola oxuyanda eyni alınırsa. Məsələn, "abba" sətiri palindromdur, amma "omax" deyil. $\alpha$ sətirinin $i$-ci mövqedən $j$-ci möqeyə qədər (mövqelər $1$-dən başlayır) alt sətirini $\alpha [i..j]$ kimi qeyd edirik. Belə alt sətirin uzunluğu j - i + 1-ə bərabərdir.

Verilmiş $n$ uzunluqlu $\alpha$ sətiri üçün elə $(i,j)$ cütlərinin sayını ($q$) tapın ki, 1 \le i < j \le n və $\alpha [i..j]$ alt sətiri palindrom olsun.