Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Ngày nay, xu hướng sử dụng smart phone đã trở thành rất phổ biến trên thế giới. Thay vì phải bấm từng phím cứng, người dùng chỉ cần chạm vào màn hình. Tuy nhiên, việc nhập sai nội dung từ xảy ra thường xuyên do không gian cho mỗi phím trên màn hình là hạn chế.

Một phần mềm sửa lỗi chính tả được người dùng khá ưa chuộng có chức năng như sau: khi người dùng nhập một từ trên màn hình, phần mềm này sẽ đưa ra danh sách các từ đúng để người dùng có thể lựa chọn. Tuy nhiên, bạn vẫn có thể cải thiện thêm tính năng cho phần mềm này, bằng cách sắp xếp các từ gợi ý theo độ ưu tiên “gần giống” với từ đã nhập nhất. Khoảng cách giữa 2 chữ cái được tính bằng tổng sai khác theo chiều ngang và chiều dọc của 2 chữ cái trên màn hình. Khoảng cách giữa 2 từ được tính bằng tổng khoảng cách của tất cả các chữ cái.

Bàn phím querty trên màn hình của điện thoại như sau:

qwertyuiop

asdfghjkl

zxcvbnm

Ví dụ, khoảng cách giữa kí tự ‘w’ và kí tự ‘e’ bằng 1, giữa ‘w’ và ‘z’bằng 3.

Input

Dòng đầu tiên là số lượng bộ test T (T <= 20).

Mỗi bộ test bằng đầu bằng một từ  (là chuỗi kí tự được nhập trên màn hình) và số nguyên n (n <= 10), là số từ gợi ý của phần mềm kiểm tra lỗi chính tả. n dòng tiếp theo, mỗi dòng là một từ gợi ý. Các từ gợi ý có chiều dài bằng với từ đã nhập ban đầu, và khác nhau đôi một.

Tất cả các chữ cái đều là chữ thường, và các từ có độ dài nhỏ hơn 10 000.

Output

Với mỗi test, in ra danh sách các từ gợi ý theo thứ tự ưu tiên tăng dần (khoảng cách so với từ đã nhập là nhỏ nhất). Nếu có nhiều từ có cùng khoảng cách với từ đã nhập, in ra theo thứ tự từ điển.

Example

Input:
2
qwertyuiopasdfghjklzxcvbnm 3
qwertyuiopsdfghjklzxcvbnma
mnbvcxzlkjhgfdsapoiuytrewq
mnbvcxzlkjhgfdsapoiuytrewa
edc 5
wsx
edc
rfv
plm
qed

Output:
qwertyuiopsdfghjklzxcvbnma 30
mnbvcxzlkjhgfdsapoiuytrewa 109
mnbvcxzlkjhgfdsapoiuytrewq 110
edc 0
rfv 3
wsx 3
qed 4
plm 17