Test Passing Probability (Large Input)

Dave is taking a multiple choice test online. He may submit his answers several times, but he passes only if one of his submissions has every question right. Every submission must carry an answer to every question, and the only thing he learns after a submission is whether he passed.

For each question Dave has estimated the probability that each of the four responses is the correct one. Those probabilities are independent of what he writes on the other questions. Given how many submissions he is allowed, Dave picks his answers so that the probability of passing is as large as possible.

Find 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 the number of submissions $M$ that Dave may make and the number of questions $Q$ on the test. $Q$ lines follow, and each of them gives, in order, the four probabilities of correctness for one question. Every probability is at least 0 and has at most six digits after the decimal point, and the four probabilities on one line sum to 1.

Constraints

• $1 \le C \le 100$
• $1 \le Q \le 30$
• $1 \le M \le 10000$

For each test case, print one line holding Case #X: Y. $X$ is the number of the test case, starting from 1. $Y$ is the largest passing probability, rounded to six digits after the decimal point and always printed with all six digits. A probability of exactly $0.5$ is printed as 0.500000.