Palindrome Trip

yum3, the worst hacker alive, is obsessed with palindromes. His own name is not one.

One day yum3 decided to travel from city s to city t. Every road in this world runs in one direction only, and each road carries a single uppercase letter. Several roads may join the same two cities, but no road starts and ends at the same city.

At each step yum3 picks one of the roads leaving his current city uniformly at random. When several roads leave a city, every one of them is equally likely, and he may pass through the same city or the same road more than once. The trip ends as soon as he arrives at city t. If he arrives at a city with no route to t at all, he stops right there. If city s has no route to t, he never moves.

Once he arrives at t, he writes the letters of the roads he used in order. If that string is a palindrome, yum3 feels lucky. If he never arrives at t, or the string is not a palindrome, he does not feel lucky. A string of one letter is a palindrome.

Find the probability that yum3 feels lucky.

The first line has the number of test cases T (1 ≤ T ≤ 100).

Each test case starts with a blank line. The next line has the number of cities n and the number of roads m (2 ≤ n ≤ 12, 0 ≤ m ≤ 1000). Cities are numbered 0 to n-1. Each of the next m lines has one road u, v, w (0 ≤ u, v < n, u ≠ v, w an uppercase letter), meaning a one-way road from city u to city v with the letter w on it. The same pair (u, v) may appear several times, and then each line is a separate road.

The next line has the number of questions q (1 ≤ q ≤ 150), and each of the following q lines has a start city s and a destination city t (0 ≤ s, t < n, s ≠ t).

For each test case, print Case x: on a line of its own, where x is the test case number starting from 1. Then print the answer to each question on its own line, in input order.

An answer is the probability that yum3 feels lucky, rounded to six digits after the decimal point. A probability of $1/3$ prints as 0.333333 and a probability of 1 prints as 1.000000. Every answer in the test data sits at least $10^{-9}$ away from a rounding boundary, so the string to print is uniquely determined.