Automat

Input

The first line contains the number of test cases $T$ (1 \leq T \leq 20). Each test case begins with a line containing four integers $A$, $B$, $C$, $N$, where $A$ is the minimum allowed temperature, $B$ is the maximum allowed temperature, $C$ is the initial temperature, and $N$ is the device's operating time in minutes. 0 \leq A \leq B \leq 30, A \leq C \leq B, 0 \leq N \leq 30.

Each of the next B-A+1 lines contains $7$ non-negative integers summing to $100$ — the percentage probabilities for temperature changes of $-4$, $-3$, $-2$, $-1$, $0$, $1$, and $2$ degrees, respectively. The $K$-th line (1 \leq K \leq B-A+1) describes these probabilities when the current temperature is A+K-1.

Output

Output $T$ lines in the format "Case #A: B", where $A$ is the test case number (starting from $1$), and $B$ is the required probability for that test case. Print the answer without rounding. It is guaranteed that the answer contains at most $60$ digits after the decimal point.

Examples