Hide

Problem H
Razbibriga

Mirko has already solved all crosswords available in daily newspapers, and he is too intimidated by ACTA to download new ones from the Internet. Now he has asked Frane to challenge him with a programming problem. Frane has eagerly responded with a brand new task, and was kind enough not to lock the task under copyright protection, so you are allowed to attempt it too!

Four words with equal lengths can be put together in a square such that two words mark horizontal edges, while the other two mark vertical edges. Horizontal words are read left to right, and vertical ones from top to bottom. Corner letters are shared by the two neighbouring edges. The figure below shows one possible square created from words “HLAD”, “NIVA”, “HSIN”, “DEDA”.

\includegraphics[width=0.3\textwidth ]{fig}

Your task is, given a list of equal-length words, to compute the number of different squares that can be put together from a subset of these words. You are not allowed to repeat a word in the same square. Two squares are different if they differ in at least one character.

Input

The first line of input contains the positive integer $N$ ($4 \le N \le 100\, 000$), the number of words in the list.

Each of the next $N$ lines contains a single word consisting only of uppercase English letters.

Each word will contain at most $10$ characters. All words will be distinct and have equal length.

Output

The first and only line of output must contain the required number of distinct squares.

The test data will be such that the solution fits in a signed $64$-bit integer.

Sample Input 1 Sample Output 1
4
NIVA
HLAD
HSIN
DEDA
2
Sample Input 2 Sample Output 2
6
BAKA
BARA
BALC
CALC
ARHC
BLIC
8

Please log in to submit a solution to this problem

Log in