Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Chikongunia

Limits: 5s, 512 MB

Chikongunia is an epidemic in Dhaka right now. Many people are affected by this. But the problem is, there is no cure so far. Team of scientists at Scientists United for Sustainable Treatment (SUST) is determined to find a cure. Now they need your help.

Scientists have discovered that chikongunia viruses can be modified to attack each other. Scientists have been able to represent each type of virus by a string of length M, consisting of only lowercase English characters. They found out that they can only make one virus attack another if their strings are different by exactly one character. That is, there will be only one place where the two string differ and all other place will be same.

Now the scientists have N viruses in an experiment. They have the string representation for each virus. Now they want to know the number of ways you can choose two viruses so that they attack each other.

Input

The first line of the input will have two integers N and M (1 <= N, M <= 100000). Then follows N lines each with M lowercase English characters. It is guaranteed that N * M <= 1000000.

Note: there is only one case per input file.

Output

The output will be one line containing the number of pair.

Samples

InputOutput
5 7
abcdefg
abcddfg
abcdddg
zxcdefg
axcdefg
4
7 3
abc
abd
abe
abf
abg
abh
abi
21

Discussion
Submit

Login to submit