Description

Given $n$ strings of length $4$, you need to find how many pairs of strings have exactly $D$ positions where the corresponding characters are different.

Input Format

The first line contains two integers $n, D$.

The next $n$ lines each contain a string of length $4$.

Output Format

Output one integer on a single line, representing the number of pairs of strings that satisfy the condition.

4 1
0000
a010
0202
a0e2

0

4 2
0000
a010
0202
a0e2

3

Hint

Sample Explanation

Sample 1 Explanation

Any two strings differ in more than one position.

Sample 2 Explanation

There are three pairs of strings: 0000,a010 a010,a0e2 0000,0202.

Constraints

• For $15\%$ of the testdata, it is guaranteed that $n \le 2000$.
• For $30\%$ of the testdata, it is guaranteed that $D = 1$.
• For $60\%$ of the testdata, it is guaranteed that $D \le 2$.
• For $75\%$ of the testdata, it is guaranteed that the strings contain only lowercase letters $a \sim f$ and digits, so they can be treated as hexadecimal numbers.
• For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 5 \times 10^4$, $1 \le D \le 4$, all input strings are distinct, and each character in the string is either $a \sim z$ or a digit character.

Notes

This problem is translated from CEOI 2010 day 2 T2 pin.

The copyright of this translation belongs to the problem provider

Translated by ChatGPT 5