시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 15 12 41.379%

문제

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

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

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

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

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+XHJcblxyXG48cD5cclxuXHRcdWI5ZGVcdWNkYTRcdWJjOTUgXHVhYzgwXHVjMGFjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCwgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YjJlOFx1YzViNCBcdWJhYTlcdWI4NWQgXHVjOTExIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzRcdWMxMWMgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkOTRcdWNjOWNcdWQ1NzQgXHVjOTAwXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM4MWNcdWM3N2MgXHViYTNjXHVjODAwIFx1YmNmNFx1YzVlY1x1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMTMwXHVjZTU4IFx1YzJhNFx1ZDA2Y1x1YjliMCBcdWQwYTRcdWJjZjRcdWI0ZGNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbnF3ZXJ0eXVpb3BcclxuYXNkZmdoamtsXHJcbnp4Y3Zibm08XC9wcmU+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCwgXHVhYzAxIFx1YjJlOFx1YzViNFx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlOFx1YzViNFx1YzY0MCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1ZDBhNFx1YmNmNFx1YjRkYyBcdWMwYzFcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHViMDdjXHViOWFjXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWJiMzhcdWM3OTBcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1ZDBhNFx1YmNmNFx1YjRkY1x1YzVkMFx1YzExYyBcdWFjMDBcdWI4NWNcdWI4NWMgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM2NDAgXHVjMTM4XHViODVjXHViODVjIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHViOTdjIFx1YjM1NFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIHdcdWI5N2MgXHVjNzg1XHViODI1XHVkNTg4XHVjNzQ0IFx1YjU0YywgZVx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgMSwgelx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgM1x1Yzc3NFx1YjJlNC4gXHViNjEwLCBpY3BjXHVjNjQwIGlmcHZcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IDNcdWM3NzRcdWIyZTQuIFx1YWM3MFx1YjlhY1x1YWMwMCBcdWFjMDBcdWFlNGNcdWM2YjggXHVjMjE4XHViODVkIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWIyZThcdWM1YjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHQgKDAgJmx0OyB0ICZsdDsgMjApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlOFx1YzViNFx1YzY0MCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IGxcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IGwgJmxlOyAxMCkgXHViMmU0XHVjNzRjIGxcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjMGFjXHVjNmE5XHVjNzkwXHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWIyZThcdWM1YjRcdWM2NDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWFjZTAsIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMCwwMDBcdWFlMDBcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM5MTFcdWJjZjVcdWI0MThcdWM1YjRcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Y2Q5NFx1Y2M5Y1x1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5N2MgXHVhYzcwXHViOWFjXHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1YyBcdWI0YTQgXHViMmU4XHVjNWI0XHVjNjQwIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViNDUwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1YWM3MFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5NjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUb3VjaHNjcmVlbiBLZXlib2FyZCIsImRlc2NyaXB0aW9uIjoiPHA+Tm93YWRheXMsIHBlb3BsZSBkbyBub3QgdXNlIGhhcmR3YXJlIGtleWJvYXJkcyBidXQgdG91Y2hzY3JlZW5zLiBVc3VhbGx5LCB0aGV5IHRvdWNoIG9uIHRoZSB3cm9uZyBsZXR0ZXJzIHdpdGggdGhlaXIgY2h1bmt5IGZpbmdlcnMsIGJlY2F1c2Ugc2NyZWVuIHNwYWNlIGlzIHByZWNpb3VzIGFuZCB0aGUgbGV0dGVycyB0aGVyZWZvcmUgdG9vIHNtYWxsLjxcL3A+XHJcblxyXG48cD5Vc3VhbGx5LCBhIHNwZWxsIGNoZWNrZXIgcnVucyBhZnRlciB0eXBpbmcgYSB3b3JkIGFuZCBzdWdnZXN0cyBvdGhlciB3b3JkcyB0byBzZWxlY3QgdGhlIGNvcnJlY3Qgc3BlbGxpbmcgZnJvbS4gWW91ciBqb2IgaXMgdG8gb3JkZXIgdGhhdCBsaXN0IHNvIHRoYXQgbW9yZSBsaWtlbHkgd29yZHMgYXJlIG9uIHRvcC48XC9wPlxyXG5cclxuPHA+VGhlIHR5cGljYWwgdG91Y2hzY3JlZW4ga2V5Ym9hcmQgbG9va3MgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cHJlPlxyXG5xd2VydHl1aW9wXHJcbmFzZGZnaGprbFxyXG56eGN2Ym5tPFwvcHJlPlxyXG5cclxuPHA+WW91IHNob3VsZCB1c2UgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIGxldHRlcnMgdG8gdHlwZSBhIHdvcmQ6IHRoZSBkaXN0YW5jZSBpcyB0aGUgc3VtIG9mIHRoZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBkaXN0YW5jZSBiZXR3ZWVuIHRoZSB0eXBlZCBhbmQgcHJvcG9zZWQgbGV0dGVyLiBBc3N1bWUgeW91IHR5cGVkIGEgdywgdGhlIGRpc3RhbmNlIHRvIGUgaXMgMSwgd2hpbGUgdGhlIGRpc3RhbmNlIHRvIHogaXMgMy48XC9wPlxyXG5cclxuPHA+VGhlIHR5cGVkIHdvcmQgYW5kIHRoZSBsaXN0IG9mIHdvcmRzIGZyb20gdGhlIHNwZWxsIGNoZWNrZXIgYWxsIGhhdmUgdGhlIHNhbWUgbGVuZ3RoLiBUaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gd29yZHMgaXMgdGhlIHN1bSBvZiB0aGUgbGV0dGVyIGRpc3RhbmNlcy4gU28gdGhlIGRpc3RhbmNlIGJldHdlZW4gaWZwdiBhbmQgaWNwYyBpcyAzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IHNwZWNpIGVzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0ICgwICZsdDsgdCAmbHQ7IDIwKS4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBzdHJpbmcgYW5kIGFuIGludGVnZXIgbCBvbiBvbmUgbGluZS4gVGhlIHN0cmluZyBnaXZlcyB0aGUgd29yZCB0aGF0IHdhcyB0eXBlZCB1c2luZyB0aGUgdG91Y2hzY3JlZW4ga2V5Ym9hcmQsIHdoaWxlIGwgc3BlY2kgZXMgdGhlIG51bWJlciBvZiBlbnRyaWVzIGluIHRoZSBzcGVsbCBjaGVja2VyIGxpc3QgKDAgJmx0OyBsICZsZTsgMTApLiBUaGVuIGZvbGxvdyBsIGxpbmVzLCBlYWNoIHdpdGggb25lIHdvcmQgb2YgdGhlIHNwZWxsIGNoZWNrZXIgbGlzdC4gWW91IG1heSBzYWZlbHkgYXNzdW1lIHRoYXQgYWxsIHdvcmRzIG9mIG9uZSB0ZXN0IGNhc2UgaGF2ZSB0aGUgc2FtZSBsZW5ndGggYW5kIG5vIHdvcmQgaXMgbG9uZ2VyIHRoYW4gMTAgMDAwIGNoYXJhY3RlcnMgKG9ubHkgbG93ZXJjYXNlICYjMzk7YSYjMzk7IC0gJiMzOTt6JiMzOTspLjxcL3A+XHJcblxyXG48cD5GdXJ0aGVybW9yZSwgZWFjaCB3b3JkIGFwcGVhcnMgZXhhY3RseSBvbmNlIGluIHRoZSBzcGVsbCBjaGVja2VyIGxpc3Qgb24gb25lIHRlc3QgY2FzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBsaXN0IG9mIHdvcmRzIHNvcnRlZCBieSB0aGVpciBkaXN0YW5jZSBhc2NlbmRpbmcuIElmIHR3byB3b3JkcyBoYXZlIHRoZSBzYW1lIGRpc3RhbmNlLCBzb3J0IHRoZW0gYWxwaGFiZXRpY2FsbHkuIFByaW50IHRoZSBkaXN0YW5jZSBvZiBlYWNoIHdvcmQgaW4gdGhlIHNhbWUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=