你一定很熟悉公平分蛋糕的方案：一个人把蛋糕切成两半，另一个人选择他想吃的那一半。这种方案被认为是公平的，因为结果中没有任何一方能声称自己拿到了较小的那部分。

然而，在 Alice 家里，规则由她制定——而且这些规则绝对不公平。她命令她的弟弟 Bob 切 $n$ 刀，而不是一刀。现在，对于每一刀，Alice 都会选择其中一侧，并吃掉该侧所有的蛋糕。在 Alice 处理完所有的切口后，剩下的蛋糕归 Bob 吃。

蛋糕在笛卡尔坐标系中表示为一个正方形（当然，实际上它是一个长方体，但我们假设所有的切口都垂直于表面），边长为 $M$。Bob 刚刚切了 $n$ 刀，现在轮到 Alice 做选择了。如果 Alice 选择明智，确定她能吃掉多少蛋糕。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 500$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ ($1 \le n \le 4000$) 和 $M$ ($1 \le M \le 1000$)，分别表示切的刀数和蛋糕的边长。蛋糕是一个正方形，其相对的顶点位于 $(0, 0)$ 和 $(M, M)$。

接下来有 $n$ 行，第 $i$ 行包含三个整数 $A_i$、$B_i$ 和 $C_i$ ($-1000 \le A_i, B_i \le 1000, -10^6 \le C_i \le 10^6, A_i^2 + B_i^2 > 0$)，定义了第 $i$ 刀的直线方程 $A_ix + B_iy + C_i = 0$。

更准确地说，Alice 得到了一组 $n$ 个直线方程。对于每个方程，她需要将 $=$ 运算符替换为 $\le$ 或 $\ge$，从而得到一个半平面方程。蛋糕与这 $n$ 个半平面的交集就是 Alice 可以吃掉的部分。

每一刀都将蛋糕切成两个面积非零的部分。

所有测试用例中的切刀总数不超过 $10\,000$。

输出格式

对于每个测试用例，输出一行，包含一个实数 $P$ ($0 \le P \le 100$)，保留 6 位小数，后跟一个 '%' 符号，表示如果 Alice 做出最优选择，她能吃掉的蛋糕百分比。如果 $P$ 与正确百分比的误差不超过 $0.000002\%$，则你的解将被接受。

样例

输入 1

1
2 1000
0 1 -750
1 0 -750

输出 1

93.750000%