Polindromlar

Sətir o zaman polindrom adlanır ki, o soldan sağa və sağdan sola eyni oxunsun. Məsələn, "abba" — polindromdur, "omax" isə yox. $a$ sətri üçün onun $j-i+1$ alt sətrini ($i$-dən $j$ mövqeyə qədər) (mövqelər $1$-dən başlayaraq nımrələnir) $\alpha [i..j]$ adlandıracağıq.

Uzunluğu $n$ olan $a$ sətri üçün polindrom olan $q$ cütlüklərinin $(i,j)$, $1\le i<j\le n$, belə ki, $\alpha [i..j]$ sajını tapmaq tələb olunur.

Giriş verilənləri

Kiçik latın hərfləri ehtiva edən $n(1\le n\le 10^5)$ uzunluqda $a$ sətri verilir.

Çıxış verilənləri

Tələb olunan $q$ cütlüklərinin sayı.

Nümunələr