kaos

Little Lovro likes to play games with words. During the last few weeks he realized that some words don't like each other.

The words A and B don't like each other if the word A is lexicographically before the word B, but the word B' is lexicographically before the word A', where X' stands for the word X reversed (if X = “kamen”, then X' = “nemak”). For example, the words “lova” and “novac” like each other, but the words “aron” and “sunce” don't like each other.

Given some set of the words, we define the degree of chaos of the set as the number of pairs of different words that don't like each other.

Write a program that, given a set of words, finds the chaos degree for the set.

input data

The first line of input contains an integer N, 2 ≤ N ≤ 100 000.

Each of the following N lines contains one word – a sequence of at most 10 lowercase letters of the English alphabet ('a' – 'z'). There will be no two identical words in the set.

output data

The first and only line of output should contain a single integer – the chaos degree of the given set of words.

Note: use 64-bit signed integer type (int64 in Pascal, long long in C/C++)

examples

input                                          input                                       input

2                                                  4                                             14

lopta                                           lova                                          branimir

kugla                                          novac                                       vladimir

                                                  aron                                          tom

output                                       sunce                                        kruz

0                                                                                                  bred

                                                  output                                       pit

                                                  3                                                zemlja

                                                                                                    nije

                                                                                                   ravna

                                                                                                  ploca

                                                                                                  ko

                                                                                                  je

                                                                                                   zapalio

                                                                                                   zito

                                                                                                 output

                                                                                                    48