The first line of the input contains two space-separated positive integers $N$ and $D$, where $N$ is the number of PINs and $D$ is the chosen number of differences. Each of the following $N$ lines contains a single PIN.
Comet OJ
Martin has just been hired as a computer administrator in a big company. The company did not change its authorization system since 1980s. Every person has a four-digit personal identification number (PIN). Nobody uses usernames or passwords, you can login just by typing your PIN. As the company grew, they added the possibility to use letters as well, but the length of the PIN remained the same.
Martin is not happy with the situation. Suppose there are people whose PINs differ only at a single place, for example 61ab and 62ab. If the first person accidentally presses 2 instead of 1, the system would still let him in. Martin would like to make the statistics about the PINs currently in use, in particular, compute the number of pairs of PINs that differ at 1, 2, 3 or 4 positions. He hopes that these numbers will be alarming enough to convince his boss to invest in a better system.
Task specification
Given the list of PINs and an integer $D$, find the number of pairs of PINs that differ at exactly $D$ positions.
The first line of the input contains two space-separated positive integers $N$ and $D$, where $N$ is the number of PINs and $D$ is the chosen number of differences. Each of the following $N$ lines contains a single PIN.
Output a single line with a single number: the number of pairs of PINs that differ at exactly $D$ positions.
4 1
0000
a010
0202
a0e204 2
0000
a010
0202
a0e23Explanation
Sample 1:
For these PINs each pair of PINs differs at more than one position.
Sample 2:
There are three pairs that differ at exactly 2 positions: (0000,a010), (0000,0202), and (a010,a0e2).
Constraints
You may assume that in all test cases $2 \le N \le 50000$ and $1 \le D \le 4$.
Each PIN is of length 4 and each character is either a digit or a lowercase letter between 'a' and 'z', inclusive. You may assume that all PINs in the input are different.
In test cases worth 15 points, $N \le 2000$.
In test cases worth 60 points, $D \le 2$. Out of those, in test cases worth 30 points, $D = 1$.
In test cases worth 75 points, every PIN will only consist of digits or lowercase letters between 'a' and 'f', inclusive. Thus it can be viewed as a hexadecimal number.