Count Compatible Palindrome Pairs

You are given n strings consisting of lowercase Latin letters. Two strings a and b are considered compatible if the concatenation ab (i.e. string a followed by string b) forms a palindrome. Formally, a string S is a palindrome if \(S = S^R\), where \(S^R\) denotes the reverse of \(S\).

Your task is to count the number of ordered pairs \((i,j)\) (with \(1 \le i, j \le n\)) such that the concatenation of the \(i\)-th and \(j\)-th string is a palindrome. Note that if \(i \neq j\), the pairs \((i,j)\) and \((j,i)\) are counted separately. In the case \(i=j\), simply count the pair if the string concatenated with itself forms a palindrome.

Input Format: The input is given from stdin and consists of an integer \(n\) on the first line followed by \(n\) lines, each containing a string.

Output Format: Output a single integer representing the number of compatible pairs.

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq 10^5)\) representing the number of strings. Each of the following \(n\) lines contains a non-empty string made up of lowercase letters.

outputFormat

Output a single integer which is the number of pairs \((i,j)\) such that the concatenation of the i-th string and j-th string forms a palindrome.

3
abc
cba
bca

2