Similar Words

Interview

Time limit2sMemory limit128 MB

Summary
Count unordered pairs of equal-length words that are related by some bijection between letters, similar to the isomorphic-strings check.
Level

Medium4 of 10

Topics
String, Hash map, Combinatorics
Solved
No attempts yet

Problem

Two words A and B are similar if it is possible to assign one lowercase letter to each distinct letter in A so that replacing every letter of A by its assigned letter produces B.

Equal letters in A must therefore become equal letters in B, and two different letters in A may not become the same letter in B. A letter may be assigned to itself.

For instance, assign a to z, b to b, and c to x in abca. The result is zbxz, so abca and zbxz are similar.

Given several words, count how many unordered pairs of words are similar.

Input

The first line contains the number of words N. Each of the next N lines contains one word.

N is a positive integer not greater than 100. Each word has length at most 50. All words have the same length, no two words are identical, and every word consists only of lowercase English letters.

Output

Print the number of unordered pairs of similar words.

Examples3

  1. Example 1

    Input
    5
aa
ab
bb
cc
cd
    Expected output
    4

  2. Example 2

    Input
    3
abca
zbxz
opqr
    Expected output
    1

  3. Example 3

    Input
    12
cacccdaabc
cdcccaddbc
dcdddbccad
bdbbbaddcb
bdbcadbbdc
abaadcbbda
babcdabbac
cacdbaccad
dcddabccad
cacccbaadb
bbcdcbcbdd
bcbadcbbca
    Expected output
    13