혼동하기 쉬운 로그인 이름

메이쿄칸 대학교(Meikyokan University)는 컴퓨터 과학 분야의 연구와 교육으로 매우 유명합니다. 이 대학교에는 슈퍼컴퓨터와 인터넷에 연결된 다수의 개인용 컴퓨터를 포함한, 발전되고 안전한 컴퓨팅 시설을 갖춘 전산 센터가 있습니다.

전산 센터의 방침 중 하나는 학생들이 자신의 로그인 이름을 직접 고르게 하는 것입니다. 그런데 학생들은 서로 비슷한 로그인 이름을 고르는 경향이 있어, 로그인 이름을 입력하거나 지정할 때 실수로 인한 문제가 비교적 자주 발생합니다. 이러한 문제들은 전산 센터 직원들에게 부담이 됩니다.

이런 문제를 피하기 위해, 전산 센터의 총괄 책임자인 다카노 초에이(Choei Takano) 박사는 서로 비슷하고 혼동하기 쉬운 로그인 이름을 없애기로 했습니다. 이를 위해 다카노 박사는 혼동하기 쉬운 로그인 이름을 찾아내는 프로그램을 개발해야 합니다.

문자열에 대한 다음 네 가지 연산을 바탕으로, 두 로그인 이름 사이의 거리를 한 로그인 이름을 다른 로그인 이름으로 변환하는 데 필요한 최소 연산 횟수로 정의합니다.

1. 임의의 위치에 있는 문자 하나를 삭제하기.
2. 임의의 위치에 문자 하나를 삽입하기.
3. 임의의 위치에 있는 문자 하나를 다른 문자로 교체하기.
4. 임의의 위치에서 인접한 두 문자의 자리를 서로 바꾸기.

예를 들어, "omura"와 "murai" 사이의 거리는 2입니다. 다음과 같은 연산 순서로 "omura"를 "murai"로 변환할 수 있기 때문입니다.

omura → ('o' 삭제) → mura → ('i' 삽입) → murai

또 다른 예로, "akasan"과 "kaason" 사이의 거리도 2입니다.

akasan → ('a'와 'k' 자리 바꾸기) → kaasan → ('a'를 'o'로 교체) → kaason

다카노 박사는 거리가 작은 두 로그인 이름은 혼동하기 쉬우므로 피해야 한다고 판단했습니다.

여러분의 임무는 혼동하기 쉬운 모든 로그인 이름 쌍을 열거하는 프로그램을 작성하는 것입니다.

규칙들이 미묘하게 결합될 수 있으니 주의하세요. 예를 들어 "ant"와 "neat" 사이의 거리는 2입니다.

ant → ('a'와 'n' 자리 바꾸기) → nat → ('e' 삽입) → neat

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋은 다음 형식으로 주어집니다.

n
d
name1
name2
···
namen

첫 번째 정수 $n$은 로그인 이름의 개수입니다. 그 다음에는 양의 정수 $d$가 옵니다. 거리가 $d$ 이하인 두 로그인 이름은 혼동하기 쉬운 것으로 간주합니다. $0 < n \le 200$이고 $0 < d \le 2$라고 가정해도 됩니다. $i$번째 학생의 로그인 이름은 $\text{name}_i$로 주어지며, 소문자로만 이루어져 있습니다. 그 길이는 $16$ 미만입니다. $\text{name}_i$ ($1 \le i \le n$)에는 중복이 없다고 가정해도 됩니다.

입력의 끝은 $0$ 하나만 있는 줄로 표시됩니다.

각 데이터셋에 대해, 프로그램은 혼동하기 쉬운 로그인 이름의 모든 쌍을 한 줄에 하나씩 출력하고, 이어서 해당 데이터셋의 혼동하기 쉬운 쌍의 총 개수를 출력해야 합니다.

각 쌍에서 두 로그인 이름은 쉼표(,) 하나로만 구분하며, 사전순으로 앞서는 로그인 이름을 먼저 씁니다. 각 데이터셋에 대한 혼동하기 쉬운 쌍 전체 출력은 다음과 같이 정렬해야 합니다. 두 쌍 "w1,w2"와 "w3,w4"에 대해, w1이 사전순으로 w3보다 앞서거나, 둘이 같고 w2가 w4보다 앞선다면, "w1,w2"가 "w3,w4"보다 먼저 나와야 합니다.