There is a collection of non-empty strings ~S~ that are indexed from ~1~ to ~N~ (where ~N~ is the number of strings). Count how many ordered triples of indices ~(i,j,k)~ (with repetition allowed) produce a palindrome of odd length when concatenated as ~S_i + S_j + S_k~.

Input Specification

The first line of input contains an integer ~N~, the number of strings in ~S~. The following ~N~ lines of input consist of 1 or more lowercase letters each, where the ~i~-th line contains the string ~S_i~ (string indexed at ~i~). The total number of letters in all of the strings put together will be at most ~100\,000~.

Output Specification

Output a single integer, the number of such triplets.

Sample Input 1

4
a
ab
ba
cc

Sample Output 1

6

Explanation for Sample Output 1

The valid triplets are ~(1,1,1), (1,3,3), (2,1,3), (2,2,1), (3,1,2), (4,1,4)~.

Sample Input 2

2
a
a

Sample Output 2

8

Explanation for Sample Output 2

The valid triplets are ~(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)~.