When browsing the BBS (what is BBS? if you want to know you can view Wiki), we usually see many similar ID. And most of these IDs are just "multi"(duplicated account that looks similar) of some others.
Now we give a checklist of detecting whether an ID is a "multi" of another ID. The method is following:
There are three kinds of steps for modifying an id and each kind of operations have its own cost:
Adding a valid character in any position of the id. it costs 2 points.
Delete a character in any position of the id. it costs 2 points.
some of characters can change each other. These characters are:
"O" <-> "0", "l" <-> "1", "Z" <-> "2", "E" <-> "3", "R" <-> "4",
"S" <-> "5", "b" <-> "6", "J" <-> "7", "B" <-> "8", "q" <-> "9". It costs 1 point.
If an ID can be obtained from another using no more than 3 points, then the two IDs are "multi"s of each other.
Given the list of All IDs in a BBS station,for each query you must to find the number of IDs which might be the "multi" of the specified ID in this query.
A valid ID is combine by capital characters or lowercase charcter or digital number which lenth between 1 and 12 (inclusive). (the lowercase and capital character is not equivalent).
The first line of input contain T,denoting the number of test cases.
Each test case contains two parts. In the first part, containing All IDs in the BBS station. Each line contains one ID. The part end with a string "===". The second part contains these IDs queried. Each line contain one ID which occur in the IDs list. The part also end with a string "===".
T<=5
There are at most 200000 ID in a BBS station.
All IDs in the list are different.
There are at most 1000 queries in all test cases.
For each query, print a line contain an integer denoting the number of IDs which might be the "multi" of the specified ID in this query.
1 tmt514 tmt415 tmtS14 tmtSl4 tmt5l4 tmtr44 darktmt kelvin ke0vin ke1vin ke2vin killvin ke1tmt dreamoon dreamon dreamooon dreamoooon pipi === tmt514 ke1vin dreamoon pipi ===
3 1 2 0
In the sample input, "tmtS14","tmtSl4","tmt5l4" are the "multi" of tmt514.
p.s. If you want to make sure of the correct character changing, you can take use of copy and paste.
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|