p00831 Confusing Login Names
Meikyokan University is very famous for its research and education in the area of computer science. This university has a computer center that has advanced and secure computing facilities including supercomputers and many personal computers connected to the Internet.

One of the policies of the computer center is to let the students select their own login names. Unfortunately, students are apt to select similar login names, and troubles caused by mistakes in entering or specifying login names are relatively common. These troubles are a burden on the staff of the computer center.

To avoid such troubles, Dr. Choei Takano, the chief manager of the computer center, decided to stamp out similar and confusing login names. To this end, Takano has to develop a program that detects confusing login names.

Based on the following four operations on strings, the distance between two login names is determined as the minimum number of operations that transforms one login name to the other.

1. Deleting a character at an arbitrary position.
2. Inserting a character into an arbitrary position.
3. Replacing a character at an arbitrary position with another character.
4. Swapping two adjacent characters at an arbitrary position.



For example, the distance between “omura” and “murai” is two, because the following sequence of operations transforms “omura” to “murai”.


delete ‘o’        insert ‘i’
omura      -->        mura      -->      murai


Another example is that the distance between “akasan” and “kaason” is also two.


swap ‘a’ and ‘k’         replace ‘a’ with ‘o’
akasan        -->           kaasan       -->               kaason


Takano decided that two login names with a small distance are confusing and thus must be avoided.

Your job is to write a program that enumerates all the confusing pairs of login names.

Beware that the rules may combine in subtle ways. For instance, the distance between “ant” and “neat” is two.


swap ‘a’ and ‘n’      insert ‘e’
ant         -->         nat      -->      neat




Input

The input consists of multiple datasets. Each dataset is given in the following format.


n
d
name1
name2
...
namen


The first integer n is the number of login names. Then comes a positive integer d. Two login names whose distance is less than or equal to d are deemed to be confusing. You may assume that 0 < n ≤ 200 and 0 < d ≤ 2. The i-th student’s login name is given by namei, which is composed of only lowercase letters. Its length is less than 16. You can assume that there are no duplicates in namei (1 ≤ i ≤ n).

The end of the input is indicated by a line that solely contains a zero.

Output

For each dataset, your program should output all pairs of confusing login names, one pair per line, followed by the total number of confusing pairs in the dataset.

In each pair, the two login names are to be separated only by a comma character (,), and the login name that is alphabetically preceding the other should appear first. The entire output of confusing pairs for each dataset must be sorted as follows. For two pairs “w1,w2” and “w3,w4”, if w1 alphabetically precedes w3, or they are the same and w2 precedes w4, then “w1,w2” must appear before “w3,w4”.

Example

Input

8
2
omura
toshio
raku
tanaka
imura
yoshoi
hayashi
miura
3
1
tasaka
nakata
tanaka
1
1
foo
5
2
psqt
abcdef
abzdefa
pqrst
abdxcef
0


Output

imura,miura
imura,omura
miura,omura
toshio,yoshoi
4
tanaka,tasaka
1
0
abcdef,abdxcef
abcdef,abzdefa
pqrst,psqt
3
```python
from collections import Counter
from itertools import permutations
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    def dist(a, b):
        LA = len(a); LB = len(b)
        dp = [[10**18]*(LB+1) for i in range(LA+1)]
        dp[0][0] = 0
        for i in range(LA):
            for j in range(LB):
                v = dp[i][j]
                if a[i] == b[j]:
                    dp[i+1][j+1] = min(dp[i+1][j+1], v)
                else:
                    dp[i+1][j+1] = min(dp[i+1][j+1], v+1)
                dp[i+1][j] = min(dp[i+1][j], v+1)
                dp[i][j+1] = min(dp[i][j+1], v+1)
            dp[i+1][LB] = min(dp[i+1][LB], dp[i][LB]+1)
        for j in range(LB):
            dp[LA][j+1] = min(dp[LA][j+1], dp[LA][j] + 1)
        return dp[LA][LB]
    def check(a, b):
        LA = len(a); LB = len(b)
        if abs(LA - LB) > D:
            return False
        d = dist(a, b)
        if d <= D:
            return True
        if d == 2 and LA == LB:
            ra = []; rb = []; rp = []
            for i in range(LA):
                if a[i] != b[i]:
                    rp.append(i)
                    ra.append(a[i])
                    rb.append(b[i])
            if len(rp) == 2 and rp[1] - rp[0] == 1:
                ra.reverse()
                if ra == rb:
                    return True
        if D == 2:
            if d == 4 and LA == LB:
                ra = []; rb = []; rp = []
                for i in range(LA):
                    if a[i] != b[i]:
                        rp.append(i)
                        ra.append(a[i])
                        rb.append(b[i])
                if len(rp) == 4 and rp[1] - rp[0] == 1 and rp[3] - rp[2] == 1:
                    ra[0], ra[1] = ra[1], ra[0]
                    ra[2], ra[3] = ra[3], ra[2]
                    return ra == rb
            if d == 3 and abs(LA - LB) < D:
                a = list(a); b = list(b)
                if not LA < LB:
                    LA, LB = LB, LA
                    a, b = b, a
                for i in range(LA-1):
                    a[i], a[i+1] = a[i+1], a[i]
                    if dist(a, b) <= D-1:
                        return True
                    for j in range(LA-1):
                        a[j], a[j+1] = a[j+1], a[j]
                        if a == b:
                            return True
                        a[j], a[j+1] = a[j+1], a[j]
                    a[i], a[i+1] = a[i+1], a[i]
        return False
    D = int(readline())
    S = [readline().strip() for i in range(N)]
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            if check(S[i], S[j]):
                ans.append((S[i], S[j]) if S[i] < S[j] else (S[j], S[i]))
    ans.sort()
    for e in ans:
        write("%s,%s\n" % e)
    write("%d\n" % len(ans))
    return True
while solve():
    ...

```