Konstantin 和 Ilia 住在同一栋房子里。Konstantin 住在楼上，喜欢跳跃、搬动家具等会制造噪音的活动。Ilia 住在楼下，喜欢睡觉。

为了度过一个愉快的夜晚，Konstantin 想要进行至少 $K$ 项活动。昨晚，Ilia 请求 Konstantin 尽量不要吵醒他；由于 Konstantin 是一位非常友好的邻居，他答应了。不幸的是，他把 Ilia 的请求理解得有点太字面了，他将选择他的活动，以最小化 Ilia 入睡后被吵醒的概率。

Konstantin 的每项可能活动都有一个关联概率 $a_i/b_i$。如果 Konstantin 执行了这项活动，那么在活动结束时，Ilia 将以 $a_i/b_i$ 的概率处于清醒状态，否则处于睡眠状态，无论他在活动开始时是否处于睡眠状态。此外，对于每项可能的活动，Konstantin 最多只能执行 $c_i$ 次（超过这个次数会很无聊，如果感到无聊，Konstantin 就无法度过一个愉快的夜晚）。

Konstantin 想要按顺序选择一定数量的活动，使得： 执行的活动总数至少为 $K$。 第 $i$ 项活动执行的次数不超过 $c_i$。 * Ilia 在活动过程中被吵醒一次或多次的概率 $Q$ 尽可能小。

Ilia 开始时是清醒的，因此要让他被吵醒，他必须在某项活动结束时处于睡眠状态，然后在下一项活动结束时处于清醒状态。

Konstantin 在度过愉快夜晚的同时能达到的最小 $Q$ 是多少？注意，Konstantin 无法判断 Ilia 是清醒还是睡眠，因此他无法利用这些信息来调整他的活动。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$。接下来的 $N$ 行，每行代表一项 Konstantin 可以选择的活动。这些行的格式为 "$a_i/b_i$ $c_i$"，表示有一项活动，执行后 Ilia 以 $a_i/b_i$ 的概率处于清醒状态，且 Konstantin 最多可以执行该活动 $c_i$ 次而不会感到无聊。

输出格式

对于每个测试用例，输出一行 "Case #x: Q"，其中 $x$ 是用例编号（从 1 开始），$Q$ 是 Konstantin 执行活动期间 Ilia 被吵醒的最小概率。绝对误差或相对误差不超过 $10^{-6}$ 的答案将被接受。

数据范围

内存限制：1GB。

$1 \le T \le 100$。 $0 \le a_i \le b_i \le 1000000$，对于所有 $i$。 $1 \le b_i$ 且 $1 \le c_i$，对于所有 $i$。 $1 \le K \le$ 该测试用例中所有 $c_i$ 之和。

子任务 1

时间限制：6 秒。 $1 \le N \le 100$。 每个测试用例中所有 $c_i$ 之和不超过 100。

子任务 2

时间限制：12 秒。 $1 \le N \le 10000$。 每个测试用例中所有 $c_i$ 之和不超过 $10^6$。

样例

样例输入 1

3
4 1
1/2 3
1/5 2
2/5 1
2/2 2
3 2
1/2 2
1/3 2
3/4 2
3 3
99/100 1
1/2 2
1/50 3

样例输出 1

Case #1: 0.000000000
Case #2: 0.083333333
Case #3: 0.015000000