ROT13

Interview

Time limit1sMemory limit128 MB

Summary

Given a list of lowercase words, count ordered pairs (w1, w2) from the list where w2 equals the ROT13 encoding of w1.

Level: Medium4 of 10
Topics: Hash map, String, Implementation, Math
Solved: No attempts yet

Problem

The Byteland Aircraft Factory has developed a new kind of jet plane. Naming planes with numbers is no longer fashionable, so the management decided to give each plane a two-word name. To catch the eye of potential clients, the name must have a special property: after being encoded with the ROT13 cipher it should still make sense, meaning the encoded name may differ from the original only in the order of its two words.

The ROT13 cipher replaces each letter with the one 13 positions further along the alphabet. Precisely, it follows the table below.

Letter type	Alphabet
original letter	`abcdefghijklmnopqrstuvwxyz`
encoded letter	`nopqrstuvwxyzabcdefghijklm`

Write a program that:

reads the list of available words from standard input,
computes the number of different possible plane names,
writes the result to standard output.

A name is an ordered pair of words $(w_1, w_2)$ , and both words must come from the given list. Encoding the whole name gives $(\mathrm{ROT13}(w_1), \mathrm{ROT13}(w_2))$ , which must be a reordering of the original two words. Because ROT13 never maps a letter to itself, keeping the same order is impossible, so the condition is exactly $w_2 = \mathrm{ROT13}(w_1)$ . The names $(w_1, w_2)$ and $(w_2, w_1)$ count as two different names.

Input

The first line contains an integer $n$ ( $1 \le n \le 1000000$ ). Each of the next $n$ lines contains one word made of lowercase English letters. Every word has at least one letter. The total length of all words does not exceed $1000000$ .

Output

Print a single integer on one line: the total number of different possible plane names.

Examples3

Example 1
Input
```
5
urwany
hejnal
pijany
krolik
gizmo
```
Expected output
```
2
```
Example 2
Input
```
2
a
n
```
Expected output
```
2
```
Example 3
Input
```
2
abc
def
```
Expected output
```
0
```