Palindromes

Little Johnny enjoys playing with words. He has chosen $n$ palindromes (a palindrome is a word that reads the same forwards and backwards, such as dad, eye, or racecar). He then formed all $n^2$ ordered pairs of them and, for each pair, concatenated the two palindromes in order into a single word. Finally, he counted how many of the resulting words are themselves palindromes. Johnny is not sure he did this without a mistake, so he has asked you to repeat exactly the same steps and report the result.

Write a program which:

• reads Johnny's palindromes from the standard input,
• determines how many of the words formed by concatenating an ordered pair of the input palindromes are themselves palindromes,
• writes the result to the standard output.

The first line of the standard input contains a single integer $n$ ($n \ge 2$), the number of palindromes Johnny has chosen. Each of the following $n$ lines describes one palindrome: the $(i+1)$-st line contains a positive integer $a_i$, the length of the $i$-th palindrome, followed by a single space and a palindrome consisting of $a_i$ lowercase English letters. The palindromes on different lines are all distinct. The total length of all palindromes does not exceed 2,000,000.

Print a single integer on the first line: the number of ordered pairs of palindromes whose concatenation is itself a palindrome. A pair $(i, j)$ may have $i = j$, and when $i \ne j$ the pairs $(i, j)$ and $(j, i)$ are counted separately.