Processing math: 100%
Palindrome pairs - MarisaOJ: Marisa Online Judge

Palindrome pairs

Time limit: 1000 ms
Memory limit: 512 MB

Given n string Si. Count the number of pairs i≠j that SiSj is a palindrome. (i,j) is different from (j,i).

Input

  • The first line contains an integer n.
  • The next n lines, each line contains a string Si, each string contains only lowercase letters.

Output

  • Print the number of pairs.

Constraints

  • 1≤n≤105.
  • 1≤∑|Si|≤106

Example

Input:

3
a
b
ab

Output:

2