\(5^{th}\) round, March \(17^{th}\), 2012

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”.

Your task is, given a list of equ\(al-le\)ngth 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.

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.

The first and only line of output must contain the required number of distinct squares.
Note: Test data will ensure that the solution fits in a \(64-bi\)t integer data type (int64 in Pascal, long long
in \(C/C\)++).

생성자가 기록되지 않았습니다.

출처 COCI 2011/2012 Contest 5