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.

Sample Input |
Sample Output |

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.