시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 37 18 15 46.875%

문제

요즘 사람들은 터치 스크린 키보드를 사용한다. 하지만, 터치 스크린은 버튼과 버튼 사이의 간격이 작고, 버튼의 크기가 작기 때문에 오타가 너무 많이 난다.

상근이는 오타를 줄여주기 위해서 맞춤법 검사 프로그램을 만들었다. 이 프로그램은 이름은 맞춤법 검사이지만, 실제로는 오타만 검사한다.

맞춤법 검사 프로그램은 사용자가 단어를 입력하면, 프로그램이 가지고 있는 올바른 단어 목록 중 길이가 같으면서 비슷한 단어를 추천해 준다. 이때, 가장 비슷한 단어를 제일 먼저 보여준다.

터치 스크린 키보드는 다음과 같이 생겼다.

qwertyuiop
asdfghjkl
zxcvbnm

사용자가 단어를 입력하면, 각 단어와의 거리를 계산할 수 있다. 단어와 단어의 거리는 키보드 상에서 문자끼리의 거리의 합이다. 문자와 문자의 거리는 키보드에서 가로로 떨어져 있는 거리와 세로로 떨어져 있는 거리를 더하면 된다. 예를 들어, w를 입력했을 때, e와의 거리는 1, z와의 거리는 3이다. 또, icpc와 ifpv의 거리는 3이다. 거리가 가까울 수록 비슷한 단어이다.

입력

첫째 줄에 테스트 케이스의 개수 t (0 < t < 20)가 주어진다. 각 테스트 케이스의 첫째 줄에는 사용자가 입력한 단어와 프로그램이 가지고 있는 단어의 개수 l이 주어진다. (0 < l ≤ 10) 다음 l개의 줄에는 단어가 주어진다. 이 단어는 사용자가 입력한 단어와 길이가 모두 같고, 알파벳 소문자로만 이루어져 있다. 길이는 최대 10,000글자이다. 또, 같은 단어가 중복되어서 등장하지 않는다.

출력

각 테스트 케이스에 대해서, 추천하는 단어를 거리순으로 정렬한 뒤 단어와 거리를 출력한다. 만약, 두 단어가 같은 거리를 거지고 있다면, 사전 순으로 정렬한다.

예제 입력 1

2
ifpv 3
iopc
icpc
gcpc
edc 5
wsx
edc
rfv
plm
qed

예제 출력 1

icpc 3
gcpc 7
iopc 7
edc 0
rfv 3
wsx 3
qed 4
plm 17
W3sicHJvYmxlbV9pZCI6IjM5NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxMzBcdWNlNThcdWMyYTRcdWQwNmNcdWI5YjAgXHVkMGE0XHViY2Y0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM2OTRcdWM5OTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1ZDEzMFx1Y2U1OCBcdWMyYTRcdWQwNmNcdWI5YjAgXHVkMGE0XHViY2Y0XHViNGRjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWQxMzBcdWNlNTggXHVjMmE0XHVkMDZjXHViOWIwXHVjNzQwIFx1YmM4NFx1ZDJiY1x1YWNmYyBcdWJjODRcdWQyYmMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWMwNFx1YWNhOVx1Yzc3NCBcdWM3OTFcdWFjZTAsIFx1YmM4NFx1ZDJiY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjNzkxXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM2MjRcdWQwYzBcdWFjMDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc3NCBcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2MjRcdWQwYzBcdWI5N2MgXHVjOTA0XHVjNWVjXHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWI5ZGVcdWNkYTRcdWJjOTUgXHVhYzgwXHVjMGFjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHVjNzc0XHViOTg0XHVjNzQwIFx1YjlkZVx1Y2RhNFx1YmM5NSBcdWFjODBcdWMwYWNcdWM3NzRcdWM5YzBcdWI5Y2MsIFx1YzJlNFx1YzgxY1x1Yjg1Y1x1YjI5NCBcdWM2MjRcdWQwYzBcdWI5Y2MgXHVhYzgwXHVjMGFjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5ZGVcdWNkYTRcdWJjOTUgXHVhYzgwXHVjMGFjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCwgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YjJlOFx1YzViNCBcdWJhYTlcdWI4NWQgXHVjOTExIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzRcdWMxMWMgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkOTRcdWNjOWNcdWQ1NzQgXHVjOTAwXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWJlNDRcdWMyYjdcdWQ1NWMgXHViMmU4XHVjNWI0XHViOTdjIFx1YzgxY1x1Yzc3YyBcdWJhM2NcdWM4MDAgXHViY2Y0XHVjNWVjXHVjOTAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQxMzBcdWNlNTggXHVjMmE0XHVkMDZjXHViOWIwIFx1ZDBhNFx1YmNmNFx1YjRkY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNiY1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxucXdlcnR5dWlvcFxyXG5hc2RmZ2hqa2xcclxuenhjdmJubTxcL3ByZT5cclxuXHJcbjxwPlxyXG5cdFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0LCBcdWFjMDEgXHViMmU4XHVjNWI0XHVjNjQwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMmU4XHVjNWI0XHVjNjQwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVkMGE0XHViY2Y0XHViNGRjIFx1YzBjMVx1YzVkMFx1YzExYyBcdWJiMzhcdWM3OTBcdWIwN2NcdWI5YWNcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNjQwIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVkMGE0XHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWM3MFx1YjlhY1x1YzY0MCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViMzU0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgd1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWQ1ODhcdWM3NDQgXHViNTRjLCBlXHVjNjQwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAxLCB6XHVjNjQwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAzXHVjNzc0XHViMmU0LiBcdWI2MTAsIGljcGNcdWM2NDAgaWZwdlx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgM1x1Yzc3NFx1YjJlNC4gXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMwMFx1YWU0Y1x1YzZiOCBcdWMyMThcdWI4NWQgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YjJlOFx1YzViNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMCAmbHQ7IHQgJmx0OyAyMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YzZhOVx1Yzc5MFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNjQwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggbFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsdDsgbCAmbGU7IDEwKSBcdWIyZTRcdWM3NGMgbFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjJlOFx1YzViNFx1YjI5NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlOFx1YzViNFx1YzY0MCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYWE4XHViNDUwIFx1YWMxOVx1YWNlMCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwLDAwMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzViNFx1YzExYyBcdWI0ZjFcdWM3YTVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjZDk0XHVjYzljXHVkNTU4XHViMjk0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWFjNzBcdWI5YWNcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHVkNTVjIFx1YjRhNCBcdWIyZThcdWM1YjRcdWM2NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWI0NTAgXHViMmU4XHVjNWI0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzcwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvdWNoc2NyZWVuIEtleWJvYXJkIiwiZGVzY3JpcHRpb24iOiI8cD5Ob3dhZGF5cywgcGVvcGxlIGRvIG5vdCB1c2UgaGFyZHdhcmUga2V5Ym9hcmRzIGJ1dCB0b3VjaHNjcmVlbnMuIFVzdWFsbHksIHRoZXkgdG91Y2ggb24gdGhlIHdyb25nIGxldHRlcnMgd2l0aCB0aGVpciBjaHVua3kgZmluZ2VycywgYmVjYXVzZSBzY3JlZW4gc3BhY2UgaXMgcHJlY2lvdXMgYW5kIHRoZSBsZXR0ZXJzIHRoZXJlZm9yZSB0b28gc21hbGwuPFwvcD5cclxuXHJcbjxwPlVzdWFsbHksIGEgc3BlbGwgY2hlY2tlciBydW5zIGFmdGVyIHR5cGluZyBhIHdvcmQgYW5kIHN1Z2dlc3RzIG90aGVyIHdvcmRzIHRvIHNlbGVjdCB0aGUgY29ycmVjdCBzcGVsbGluZyBmcm9tLiBZb3VyIGpvYiBpcyB0byBvcmRlciB0aGF0IGxpc3Qgc28gdGhhdCBtb3JlIGxpa2VseSB3b3JkcyBhcmUgb24gdG9wLjxcL3A+XHJcblxyXG48cD5UaGUgdHlwaWNhbCB0b3VjaHNjcmVlbiBrZXlib2FyZCBsb29rcyBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbnF3ZXJ0eXVpb3BcclxuYXNkZmdoamtsXHJcbnp4Y3Zibm08XC9wcmU+XHJcblxyXG48cD5Zb3Ugc2hvdWxkIHVzZSB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgbGV0dGVycyB0byB0eXBlIGEgd29yZDogdGhlIGRpc3RhbmNlIGlzIHRoZSBzdW0gb2YgdGhlIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR5cGVkIGFuZCBwcm9wb3NlZCBsZXR0ZXIuIEFzc3VtZSB5b3UgdHlwZWQgYSB3LCB0aGUgZGlzdGFuY2UgdG8gZSBpcyAxLCB3aGlsZSB0aGUgZGlzdGFuY2UgdG8geiBpcyAzLjxcL3A+XHJcblxyXG48cD5UaGUgdHlwZWQgd29yZCBhbmQgdGhlIGxpc3Qgb2Ygd29yZHMgZnJvbSB0aGUgc3BlbGwgY2hlY2tlciBhbGwgaGF2ZSB0aGUgc2FtZSBsZW5ndGguIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byB3b3JkcyBpcyB0aGUgc3VtIG9mIHRoZSBsZXR0ZXIgZGlzdGFuY2VzLiBTbyB0aGUgZGlzdGFuY2UgYmV0d2VlbiBpZnB2IGFuZCBpY3BjIGlzIDMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgc3BlY2kgZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHQgKDAgJmx0OyB0ICZsdDsgMjApLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIHN0cmluZyBhbmQgYW4gaW50ZWdlciBsIG9uIG9uZSBsaW5lLiBUaGUgc3RyaW5nIGdpdmVzIHRoZSB3b3JkIHRoYXQgd2FzIHR5cGVkIHVzaW5nIHRoZSB0b3VjaHNjcmVlbiBrZXlib2FyZCwgd2hpbGUgbCBzcGVjaSBlcyB0aGUgbnVtYmVyIG9mIGVudHJpZXMgaW4gdGhlIHNwZWxsIGNoZWNrZXIgbGlzdCAoMCAmbHQ7IGwgJmxlOyAxMCkuIFRoZW4gZm9sbG93IGwgbGluZXMsIGVhY2ggd2l0aCBvbmUgd29yZCBvZiB0aGUgc3BlbGwgY2hlY2tlciBsaXN0LiBZb3UgbWF5IHNhZmVseSBhc3N1bWUgdGhhdCBhbGwgd29yZHMgb2Ygb25lIHRlc3QgY2FzZSBoYXZlIHRoZSBzYW1lIGxlbmd0aCBhbmQgbm8gd29yZCBpcyBsb25nZXIgdGhhbiAxMCAwMDAgY2hhcmFjdGVycyAob25seSBsb3dlcmNhc2UgJiMzOTthJiMzOTsgLSAmIzM5O3omIzM5OykuPFwvcD5cclxuXHJcbjxwPkZ1cnRoZXJtb3JlLCBlYWNoIHdvcmQgYXBwZWFycyBleGFjdGx5IG9uY2UgaW4gdGhlIHNwZWxsIGNoZWNrZXIgbGlzdCBvbiBvbmUgdGVzdCBjYXNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGxpc3Qgb2Ygd29yZHMgc29ydGVkIGJ5IHRoZWlyIGRpc3RhbmNlIGFzY2VuZGluZy4gSWYgdHdvIHdvcmRzIGhhdmUgdGhlIHNhbWUgZGlzdGFuY2UsIHNvcnQgdGhlbSBhbHBoYWJldGljYWxseS4gUHJpbnQgdGhlIGRpc3RhbmNlIG9mIGVhY2ggd29yZCBpbiB0aGUgc2FtZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==