Dat je niz reči (w_i) dužine n. Uz pomoć ovih reči moguće je kreirati n² parova (w_i, w_j) reči, čijom konkatenacijom dobijamo reč w_ij. Napisati program koji ispituje koliko ima parova čijom konkatenacijom dobijamo palindrom. Reč s je palindrom ukoliko se čita isto i sa leve i sa desne strane (npr aabaa, a, abcba).

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulaza nalazi se prirodan broj n (n ≤ 5.000) koji označava broj reči. Svaki od narednih n redova sadrži po jednu reč. Reči su sastavljene od malih slova engleskog alfabeta i njihova dužina ne prelazi 500.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlaza ispisati broj parova čijom se konkatenacijom dobija palindrom.

Primer 1.

3
a
aa
ab

5

Objašnjenje.

Parovi koji kreiraju palindrome su (1, 1), (1, 2), (2, 1), (2, 2) i (3, 1).