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 num- bers 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 ≤ N ≤ 100) followed by the maximum price R of a single ticket (1 ≤ R ≤ 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 ≤ C ≤ 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 ≤ a,b ≤ N,a ̸= b), and the amount of money they can spend is m (1 ≤ m ≤ 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 34 NYY YNY YYN 1 131 47 NYNN YNYN
2/2 NYNY NNYN 2 1 3 10 1 4 10 Sample Output Case 1 0.250000 Case 2 0.795918 0.341108