Dave 正在参加一场互联网上的多项选择测试。Dave 可能有多次提交答案的机会，但他只有在所有题目全部答对的情况下才能通过测试。他必须回答测试中的每一道题才能进行一次提交。每次提交后，他唯一能得到的信息就是他是否通过了测试。

对于每一道题，他估计了 4 个选项中每个选项正确的概率，且这些估计独立于他对其他问题的回答。在给定允许提交次数的情况下，Dave 希望选择他的回答，以最大化通过测试的概率。

如果 Dave 采取最优策略选择回答，他通过测试的概率是多少？

输入格式

输入的第一行包含测试用例的数量 $C$。接下来是 $C$ 个测试用例。

每个测试用例的第一行包含 $M$ 和 $Q$。Dave 被允许进行 $M$ 次提交来完成测试。测试共有 $Q$ 道题。接下来的 $Q$ 行，每行包含 4 个正确概率。小数点后最多有 6 位数字。每行的概率均为非负数且总和为 1。

输出格式

对于每个测试用例，输出一行 "Case #$X$: $Y$"，其中 $X$ 是测试用例的编号（从 1 开始），$Y$ 是成功的概率。

相对误差或绝对误差不超过 $10^{-6}$ 的答案将被视为正确。

数据范围

$1 \le C \le 100$

小数据集（测试集 1 - 可见；5 分）

$1 \le Q \le 6$

$1 \le M \le 1000$

大数据集（测试集 2 - 隐藏；14 分）

$1 \le Q \le 30$

$1 \le M \le 10000$

样例

样例输入 1

3
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0

样例输出 1

Case #1: 0.625
Case #2: 1.0
Case #3: 0.5