Test Passing Probability (Small)

Dave is taking a multiple choice test online. The test has $Q$ questions and each question offers 4 responses. Every submission must answer all of the questions, and Dave passes only if every answer is correct. The only thing he learns after a submission is whether he passed.

For each question Dave knows the probability that each of the 4 responses is the correct one, independently of the other questions. Given the number of submissions $M$ he is allowed, Dave picks his answers so that the probability of passing is as large as possible.

Compute the probability that Dave passes when he picks his answers optimally.

The first line contains the number of test cases $C$. $C$ test cases follow.

The first line of each test case contains $M$ and $Q$. $M$ is the number of submissions Dave may make and $Q$ is the number of questions on the test. The next $Q$ lines each contain the 4 probabilities of correctness for one question, in the order of the responses. Each probability has at most 6 digits after the decimal point, every probability is non-negative, and the four values on a line sum to 1.

• $1 \le C \le 100$
• $1 \le Q \le 6$
• $1 \le M \le 1000$

For each test case, print one line of the form Case #X: Y, where $X$ is the test case number starting from 1 and $Y$ is the probability of passing.

Print $Y$ rounded at the seventh digit after the decimal point, with all 6 decimal digits present. A probability of exactly $1$ prints as 1.000000. In the data for this problem the true answer is at least $10^{-9}$ away from a rounding boundary.