楼上/楼下

Statement

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/b c"，表示有一项活动会使 Ilia 醒着的概率为 a$_{i}$/b$_{i}$，并且 Konstantin 最多可以进行 c$_{i}$ 次而不会感到无聊。

### 数据范围

- 1 ≤ T ≤ 100.- 0 ≤ a$_{i}$ ≤ b$_{i}$ ≤ 1000000 对所有 i。- 1 ≤ b$_{i}$ 且 1 ≤ c$_{i}$ 对所有 i。- 1 ≤ K ≤ 该测试用例中所有 c$_{i}$ 的和。- 1 ≤ N ≤ 100。- 每个测试用例中所有 c$_{i}$ 的和不超过 100。- 1 ≤ N ≤ 10000。- 每个测试用例中所有 c$_{i}$ 的和不超过 10。

按测试用例顺序逐个输出答案。对于每个测试用例，输出一行，包含 Q ，其中 Q 是 Konstantin 进行的活动过程中 Ilia 被吵醒的最小概率。绝对或相对误差不超过 10^{- 6} 的答案将被接受。

Example 1

Input

Output

0.000000000
0.083333333
0.015000000