Description

Four words of the same length can be arranged into a square, as shown in the figure below. For example, "HLAD", "NIVA", "HSIN", and "DEDA" form a $4\times 4$ square.

You are given $N$ words of the same length. Find how many different squares can be formed by choosing a subset of these words, and output the number of valid arrangements.

Note that the same square cannot contain repeated words. If two words differ in at least one character, then they are considered different words.

Input Format

The first line contains an integer $N$, which is the number of words.

The next $N$ lines each contain one word consisting of uppercase letters, as described above.

Output Format

Output one line containing an integer, the number of valid arrangements.

The answer may be very large, so you need to use long long or int64.

4
NIVA
HLAD
HSIN
DEDA

2

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

8

Hint

Constraints: $4\le N\le 10^{5}$.

Each word has at most $10$ characters.

All words consist of uppercase letters.

This problem is translated from COCI 2011/2012 #5 T4。

Translated by ChatGPT 5