Of course, they try to see each other as often as they can. To facilitate
this, the students have negotiated a deal with the coachmen. Instead of
paying the regular price for a ride from one town to another, the price is
determined by drawing a random integer between 1 and
inclusive, all
numbers being equally likely. Unfortunately, this process repeats itself
a few times whenever there is no direct connection between the towns a couple
lives in. That makes the total cost of a journey quite unpredictable.
Help the couples determine the probability that one of them can afford a one-way trip to the other one. Given the number of towns and a list of direct connections, your program is supposed to process a list of couples. For each couple, you know their budget and where they live. Of course, they will always choose a route with the least expected price. Such a route exists between any two towns.
Input
The first line contains the number of test cases that follow.
Each test case begins with a line that holds the number
of towns (
) followed by the maximum price
of a single ticket (
). The following
lines contain
characters each.
The
-th character in the
-th line of these is ``Y'' if there is
a direct connection between towns
and
, but ``N'' otherwise.
The
-th character in the
-th line is always the same as the the
-th character in the
-th line. The
-th character in the
-th
line is always ``N''.
Each test case goes on with the number
of couples on a line by itself
(
). Then for each couple there is a line that holds three
integers
,
, and
. These numbers state that one of them lives in town
,
the other one in town
(
,
), and the
amount of money they can spend is
(
).
Output
For each test case, print one line containing the word ``Case'', a single
space, and its serial number (starting with
for the first test case). Then,
output one line for each couple in this test case containing the probability
that they can afford a one-way journey according to the rules above. Your
answer is allowed to differ from the exact result by at most
. Print a
blank line after each test case.
Sample Input
Sample Output
Case 2
0.795918
0.341108