COETEST5

Tự động sửa lỗi là một chức năng tự động xác thực tính đúng đắn của văn bản, thường thấy trong các trình soạn thảo văn bản như Microsoft Word. Mục đích chính của nó là một phần của trình kiểm tra chính tả để sửa lỗi chính tả hoặc lỗi gõ thông thường, giúp tiết kiệm thời gian cho người dùng.

Chúng ta hãy cùng xem một chương trình sửa lỗi đơn giản với các quy tắc sau:

• Chương trình định nghĩa trước một tập từ điển gồm N từ.
• Nếu từ cần kiểm tra tồn tại trong từ điển thì xác định từ đó đã chính xác và không cần chỉnh sửa.
• Nếu từ cần kiểm tra không tồn tại trong từ điểm, ta sẽ thử sửa từ cần kiểm tra để tạo ra một từ có trong từ điển bằng một trong ba cách sau: 

1. Thêm một ký tự vào vị trí cuối cùng.
2. Thay thế một ký tự ở vị trí cuối cùng bằng một ký tự khác.
3. Xóa một ký tự cuối cùng.

Nếu sửa theo các cách trên tạo ra được một từ có trong từ điển thì ta sẽ chọn cách sửa đó, tuy nhiên để hạn chế trường hợp sửa không đúng ý người dùng, ta sẽ không sửa khi mà có nhiều hơn một cách sửa để tạo ra một từ trong từ điển, ví dụ có nhiều cách thêm một ký tự vào vị trí cuối cùng, hoặc nhiều cách thay thế ký tự cuối cùng, hoặc sử dụng nhiều hơn một trong ba cách trên đều tạo ra được từ trong từ điển.

[Ví dụ]

Ví dụ tập từ điển gồm 3 từ hell, hello và help, các từ trường hợp cần kiểm tra chính tả như dưới đây:

- Hello → giữ nguyên vì từ này đã tồn tại trong từ điển.

- Hel → giữ nguyên vì có nhiều hơn một cách sửa để tạo thành một từ có trong từ điển, một là thêm l để tạo thành chữ hell, hai là thêm p để tạo thành chữ help.

- Helpy → sửa được bằng cách xóa ký tự cuối để tạo thành từ help.

- Hella → giữ nguyên vì có 2 cách sửa, một là thay thế ký tự cuối a thành ký tự o để tạo thành từ hello, hai là xóa ký tự cuối a để tạo thành từ hell.

Cho thông tin về tập từ điển và các từ cần kiểm tra chính tả, trong trường hợp từ cần kiểm tra không tồn tại trong từ điển hãy xác định xem có thể sửa được từ đó hay không.

[Input]

Dòng đầu tiên là số lượng test case T (T ≤ 50). Thông tin về mỗi test case như sau:

Dòng đầu tiên gồm hai số nguyên dương N nằm trong đoạn [3, 1000] và M nằm trong đoạn [3, 100], mô tả số lượng từ có trong từ điển N và số lượng từ cần kiểm tra chính tả M.

Trong N dòng tiếp theo, mỗi dòng là một từ trong từ điển, các từ chỉ gồm các ký tự in thường a → z và có độ dài nằm trong đoạn [1,14]. Không có hai từ nào giống nhau trong bộ từ điển.

Trong M dòng tiếp theo, mỗi dòng là một từ cần kiểm tra chính tả, các từ chỉ gồm các ký tự in thường từ a → z và có độ dài nằm trong đoạn [2,15].

[Ouput]

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra “#tc”, với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra sẽ là M số nguyên dương phân biệt với nhau bởi một dấu cách, tương ứng với kết quả kiểm tra chính tả của M từ trong test case đó. Kết quả kiểm tra chính tả của mỗi từ sẽ là 1 trong 6 giá trị sau:

• 0 nếu từ cần kiểm tra đã tồn tại trong từ điển.
• 1 nếu từ cần kiểm tra chỉ có một cách sửa theo cách 1 (thêm một ký tự vào vị trí cuối).
• 2 nếu từ cần kiểm tra chỉ có một cách sửa theo cách 2 (thay thế một ký tự ở vị trí cuối bằng một ký tự khác).
• 3 nếu từ cần kiểm tra chỉ có một cách sửa theo cách 3 (xóa một ký tự ở vị trí cuối).
• 4 nếu từ cần kiểm tra không tồn tại bất kỳ một cách sửa nào trong 3 cách sửa trên.
• 5 nếu từ cần kiểm tra có nhiều hơn một cách sửa.

Example

Input:
5
5
6 5
act
acid
accept
access
absolute
absolutely
acts
acces
absolutel
acce
accep
8 9
branch
girl
solution
deficit
soldier
girlfriend
scient
scientific
gap
soldie
brancn
solutio
girlf
solution
scientist
scientific
scientifica
7 16
be
station
particularly
bad
principal
announce
treaty
announct
particularlyy
particularl
station
particularlyp
particularln
treaty
announce
principaf
announce
stationg
principal
treaty
bh
principa
bey
16 15
container
resident
complex
bring
lawn
three
presidential
scholarship
journal
wood
legitimate
elsewhere
couch
portray
too
remain
threed
complex
threeh
wood
complep
legitimate
compler
elsewhere
law
legitimaten
toy
remainf
threek
journal
remain
13 20
knowledge
grant
compare
straight
husband
pepper
easy
emphasize
dry
roughly
truly
wire
shooting
straight
truly
roughly
knowledgg
grant
shootingi
roughlr
drw
trulq
easy
straighu
dry
husband
roughly
wir
trule
trul
husband
peppe
husband

Output:
#1 3 1 5 4 1
#2 4 1 2 1 3 0 4 0 3
#3 2 3 1 0 3 2 0 0 2 0 3 0 0 2 1 3
#4 3 0 3 0 2 0 2 0 1 3 2 3 3 0 0
#5 0 0 0 2 0 3 2 2 2 0 2 0 0 0 1 2 1 0 1 0