Consider a device, which performs some work. Besides it must control its temperature. It must be neither too high nor too low. But something wrong has happened with the temperature controlling mechanisms, and now the device acts as follows. In each minute it selects one of possible actions of changing its temperatures and executes it. Each action is selected with the given probability, based on current temperature.

   The probabilities of temperature changes are given to you. Сount the probability of the event, that the temperature stays in the given range for a certain time.

   Input

   First line of input contains the quantity of tests T (1 ≤ T ≤ 20). First line for each test contains numbers A, B, C, N, where A is the minimal allowed temperature, B is the maximal allowed temperature, C is the starting temperature, N is the device's working time in minutes. 0 ≤ A ≤ B ≤ 30, A ≤ C ≤ B, 0 ≤ N ≤ 30.

   Each of the next B–A+1 lines contains 7 nonnegative integers, that sum up to 100 – percentages of changes by –4, –3, –2, –1, 0, 1 and 2 degrees correspondingly. K-th line (1 ≤ K ≤ B–A+1) describes the probabilities for situation, when current temperature is equal to A+K–1.

   Output

   Output T lines of the form "Case #A: B", where A is the number of test (beginning from 1), B is the desired probability for this test case. You must output the answer without rounding. It is guaranteed, that the answer has at most 60 decimal digits after the point.