King Bhuriwala III (KB3) is quite unhappy. His not so thin figure is causing so much trouble lately. To make the matter worse his physician has put him on a strict diet. But our great king cannot live on this mean diet; he cannot simply let go of the only enjoyment in his life. So he has come up with an alternative. KB3 has been able to convince his doctor that if he is allowed to have his regular meal then he is going to do proper excercise from now on. His doctor told him that riding cycle would be the best form of excercise for him (maybe not for the poor cycle, though).

Our KB3 has asked his mayor to build a track for him. This track will have many one way roads. KB3 does not want to look stupid, so he has specifically instructed the mayor to make the roads in such a way that once he starts his excercise on a particular day, he can never come back to a place where he had been before. Our king plans to start from one road intersection and travel whimsically until he cannot travel anymore. The king's path has to end, our king is not stupid, remember? In case you are wondering how he would get back to where he had started from, think again. Why do we have the choppers for?

The lean and mean physician cannot let KB3 get away that easy. So he gave another painful task to KB3. After KB3 finishes cycling on a particular path, he would have to tell this physician the number of that path if all the paths starting from the road intersection that KB3 started from are numbered in the alphabetical order of the path labels. A path label for a path is a string containing all the road intersections in the order they are visited. This is where KB3 needs your help.

Input
There can be multiple test cases. The first line of the input gives you the number of test cases to follow. For each of the test cases the first line gives you two integers, the number of road intersections N and the number of roads M. The road intersections are to be labeled by the first N letters (always in upper case) of the english alphabet. In the following M lines you'd be given two letters representing the directed road. Then in the following line you'd be given an integer Q giving you the number of queries (Q is the number of paths that KB3 visited in Q days). Each of the next Q lines would give you a path label that KB3 has visited. You need to find the number of that path. You can assume that there will be no invalid path labels given as input.

Output
For each query print the path label followed by the path number. You can assume that the path number will always fit in a 32 bit signed integer. Please note that the paths are numbered with natural numbers starting from 1. And the path numbering starts from the first road intersection on the path. So for a given track, there can be multiple paths that have the same number. And the ride in the chopper is not a part of the excercise, thus it does not appear in the path label.

1
5 6
AB
AC
BC
CD
CE
ED
3
ABCD
ACD
CD

ABCD: 1
ACD: 3
CD: 1

Note: For the track given in the sample input you can find 4 paths that start from A. They are: ABCD, ABCED, ACD, ACED.