A string is considered a palindrome if it is the same forwards as it is backwards. For example, aa and racecar are palindromes, while abaa and hello are not.

A string ~s~ considers a string ~t~ a friend if the concatenation of ~s~ and ~t~ ~(s + t)~ in that order results in a palindrome.

In addition, two strings ~s~ and ~t~ are close iff both of the following conditions are satisfied:

1. ~s~ considers ~t~ a friend or one the strings ~s~ considers a friend is close with ~t~.
2. ~t~ considers ~s~ a friend or one the strings ~t~ considers a friend is close with ~s~.

Given ~N~ strings labelled ~a_1, a_2, \ldots, a_N~, can you determine how many pairs of strings are close?

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~.

The next line will contain ~N~ space-separated strings ~a_i~. ~a_i~ will only contain lowercase latin characters and will contain at least one character.

We guarantee that the sum of the string lengths do not exceed ~10^6~. In other words, ~\sum_{i=1}^N |a_i| \le 10^6~.

Output Specification

Output one integer: the number of pairs of strings that are close. Note that this number may not fit in a 32-bit integer.

Subtasks

Subtask 1 [10%]

~N \le 4~

Subtask 2 [40%]

~N \le 5000~

Subtask 3 [50%]

No further constraints.

Sample Input 1

4
abb a bba bbba

Sample Output 2

6