Problem D
Randomly-priced Tickets

At the end of the Middle Ages, quite a few universities throughout Europe have already been founded. The new term has just begun, so there are a lot of freshmen around. Not everyone has been lucky to be admitted to her/his desired university. As a result, many couples are now living in separate towns.

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 $R$ 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 $N$ of towns ( $1 \le N \le 100$ ) followed by the maximum price $R$ of a single ticket ( $1 \le R \le 30$ ). The following $N$ lines contain $N$ characters each. The $j$ -th character in the $i$ -th line of these is ``Y'' if there is a direct connection between towns $i$ and $j$ , but ``N'' otherwise. The $j$ -th character in the $i$ -th line is always the same as the the $i$ -th character in the $j$ -th line. The $j$ -th character in the $j$ -th line is always ``N''.

Each test case goes on with the number $C$ of couples on a line by itself ( $1 \le C \le 1000$ ). Then for each couple there is a line that holds three integers $a$ , $b$ , and $m$ . These numbers state that one of them lives in town $a$ , the other one in town $b$ ( $1 \le a, b \le N$ , $a \neq b$ ), and the amount of money they can spend is $m$ ( $1 \le m \le 10000$ ).

Output
For each test case, print one line containing the word ``Case'', a single space, and its serial number (starting with $1$ 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 $0.001$ . Print a blank line after each test case.

Sample Input

2
3 4
NYY
YNY
YYN
1
1 3 1
4 7
NYNN
YNYN
NYNY
NNYN
2
1 3 10
1 4 10
 

Sample Output

Case 1
0.250000

Case 2
0.795918
0.341108