Html Link Resolver

Time limit: 1 Seconds

Memory limit: 32768K

The company has a lot of static web pages on its site. Hands are in the process of moving the pages into a corporate database, since they want to enhance the searching capacity within their web contents. The pages will be uniformly accessed from an URL with different query strings. However the technicians forgot to update the links and now they are all broken. Before the official release of the new website, you only have a few hours to fix everything - of course you will not do it manually, will you?

The good news is that you have an HTML parser in hand. All you need to do is to resolve the links to their new URL. There are certain facts you must take into account:

• The links never go off the website. That is, no page will link to an external resource.
• The path and filename are composed of case sensitive letters only.
• The special path . (period) refers to the current path.
• The special path .. (two periods) refers to the upper path.
• The link can be either absolute (starts with /) or relative.

1. Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

Each test case starts with integers n (0 < n <= 1,000) and m (0 < m <= 10) which are the numbers of pages and of queries, respectively.

The next n lines contain an URL each, which will always be in the absolute form. The page ID's are integers from 1 to n.

The next m lines contain a query each. A query contains a page ID (which corresponds to the page in which the link is found) and the actual link separated by a single space. The query link could be either absolute or relative.

2. Output

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each query print the ID of the page that the link points to in a single line. If such a page does not exist, print 0.

3. Sample Input

2

2 2
/FirstPage
/SecondPage
1 SecondPage
1 PageOne

2 2
/news/Programming
/news/headline/ICPC
1 /news/headline/ICPC
2 ../Programming

4. Sample Output

Case 1:
2
0

Case 2:
2
1