Hesam Dueue Bararie is the showman of a very popular TV quiz: “Bararian Nights”. In this quiz, there is a big table of letters with some words hidden in it among diagonal, vertical or horizontal directions. During the quiz, Dueue tells each one of the contestants a word and they must find the total number of occurrences of that word in the table. Recently, Milk-Farhaad has decided to participate in this TV quiz and because cheating is permitted during this quiz (!), he wants you to help him by writing a computer program. By the way, Milk-Farhaad has bought the whole dictionary and configurations of the table from Dueue. All he need is a com- puter program which calculates the total number of occurrences for each word of the dictionary in the table. You can see one sample of this table in figure 1. All occur- rences of the word “hello” are circled in that. Also, the total number of occurrences of the word “madam” is equal to 2 be- cause it must be counted twice: one from left to right and the other one from right to left. Input Figure 1. Dueue’s Table The first line of the input file is an integer 1 ≤ T ≤ 10 which is the number of test cases. The first line of each test case is an integer 1 ≤ D ≤ 15, 000 which is the number of words in the dictionary that should be used for this test case. After that, comes D lines each of which containing a word, having length of no more than 1000 characters, in the dictionary. Words are all constructed from lowercase letters: a ... z. Then, comes a line containing an integer 1 ≤ Q ≤ 100 , the total number of queries for the test case. For each query, there will be two integers 1 ≤ M, N ≤ 100 which are the number of rows and the number of columns of the table respectively. Next, there are M lines each one containing N characters representing the configuration of each table of the quiz. Output For each test case, your program should write a line with the phrase ‘Test Case #i’ in which i is the index of the current test case starting from 1. Then comes the answer for each query in that test case. The answer to each query starts with a line containing the phrase ‘Query #j’. Then, all the words from dictionary which actually occurred in the table of that query should be listed one in each line (or each in one line!) together with their total number of occurrences in the given table. These words must be sorted in alphabetical order. There should be an empty line after the output for each test case. Sample Input 1 4 hello bye one two
2/2 2 33 bye okk res 33 one wzq too Sample Output Test Case #1 Query #1 bye 1 Query #2 one 1 two 1