Description

Xiao Q (pinyin) is an administrator of the PenguinQQ website. He is studying an interesting question: which accounts were registered by the same person. After long analysis, Xiao Q found that accounts registered by the same person usually have very similar names, such as Penguin1, Penguin2, Penguin3... So he decides to first count such similar cases.

Xiao Q defines two account names to be similar if and only if the two strings have the same length and differ in exactly one position. For example, “Penguin1” and “Penguin2” are similar, while “Penguin1” and “2Penguin” are not. Given $n$ account names, he wants to know how many pairs are similar.

To simplify your work, the $n$ strings all have length $L$, and they contain only uppercase and lowercase letters, digits, the underscore, and @ — a total of $64$ characters. Moreover, no two account names are identical.

Input Format

The first line contains three positive integers $N, L, S$. Here $N$ is the number of account names, $L$ is the length of each account name, and $S$ is the alphabet size, whose value is either $2$ or $64$.

If $S$ equals $2$, account names contain only the characters 0 and 1.

If $S$ equals $64$, account names may contain uppercase and lowercase letters, digits, the underscore, and @ — a total of $64$ characters.

Then $N$ lines follow, each containing a string of length $L$ that describes an account name. It is guaranteed that the $N$ strings are pairwise distinct.

Output Format

Output a single integer on one line, the number of pairs of similar account names.

4 3 64
Fax
fax
max
mac

4

Hint

The $4$ similar pairs are: Fax and fax, Fax and max, fax and max, max and mac.

Translated by ChatGPT 5