You must have heard the 'Traveling Salesman Problem'. Here we are talking about another problem named 'Traveling Fool Problem'. Assume that there are n cities connected by m one-way roads. Each road is labeled by an uppercase English letter (i.e 'A' to 'Z'). There can be multiple roads between two cities but no roads will start and end at the same city.
Mr traveling fool starts his journey from city s and he continues his journey until he reaches t, or he reaches a city from which t is unreachable. If he is in city u, he can choose any road that starts from u with equal probability.
He may visit same city/road more than once, but once he reaches t, he immediately stops his journey and remembers the road labels he found in his path in the same order the roads were visited. If the road labels in the path he traveled form a palindrome, he finds himself lucky. If he is unable to reach t or the road labels don't form a valid palindrome, he finds himself unlucky.
Given the cities, roads, s and t, can you find the probability of Mr. Traveling Fool being lucky?
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line. Next line contains two integers n (2 ≤ n ≤ 12) and m (0 ≤ m ≤ 1000). Each of the next m lines contains two integers, u v (0 ≤ u, v < n, u ≠ v) and an uppercase English letter w, meaning that there is a one-way road from city u to city v and the road label is w.
Next line contains an integer (1 ≤ q ≤ 150) denoting the number of queries. Each of the next q lines contains two integers denoting s t (0 ≤ s, t < n, s ≠ t).
Output
For each case, print the case number first. Then for each query, print the probability as stated. Errors less than 10-4 will be ignored.
Sample
| Sample Input | Sample Output |
|---|---|
2 4 3 0 1 A 1 2 A 2 3 A 2 0 3 2 0 5 4 1 2 B 2 3 D 2 4 A 2 0 B 2 1 3 1 0 | Case 1: 1.000000 0.000000 Case 2: 0.000000 0.333333 |