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) α[i..j] adlandıracağıq.

Uzunluğu n olan a sətri üçün polindrom olan q cütlüklərinin (i, j), 1 ≤ i < j ≤ n, belə ki, α[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 ≤ n ≤ 105) uzunluqda a sətri verilir.

Çıxış verilənləri

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