头等奖

题目描述

有一个 $n$ 行 $m$ 列的网格，每个格子上有一张背面朝上的牌，牌的正面可能写着“你中奖了！”也可能写着“做宝可梦”。对于第 $i$ 行 $j$ 列的格子上的牌，有 $p_{i,j}\text{%}$ 的概率写的是“做宝可梦”。如果所有列都至少有一张牌是“你中奖了！”，那么就能获得头等奖。

糖糖每次可以翻开一个格子上的牌，来检查它到底是写着“你中奖了！”还是“做宝可梦”，由于他只关心是否能获得头等奖，所以当他发现有一列全都是“做宝可梦”或者所有列都至少出现一张“你中奖了！”，就会停止检查。由于糖糖并不傻，所以当某一列已经出现“你中奖了！”的牌，他就不会再检查这一列了。可以知道，在某种策略下，检查次数的期望最小，糖糖不是很聪明，所以你能告诉他这个期望是多少吗？

输入

第一行包含一个整数 $T$，表示数据组数。

对于每组数据，包含若干行，第一行两个正整数 $n,m$，表示网格大小。 接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列为 $p_{i,j}$ 的值。

其中，$1\le T\le 30$，$1\le n \le 10$，$1\le m\le 250$，$1\le p_{i,j}\le 99$ 。

输出

对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为输出的最小期望，当你的输出与标准输出的绝对误差或者相对误差不超过 $10^{-6}$ 时，被判定为正确。

输入样例

2
1 1
99
2 2
60 70
90 80

输出样例

Case #1: 1.0
Case #2: 2.382