「公平なケーキカット」という手法はよくご存知でしょう。一人がケーキを2つに切り分け、もう一人が好きな方を選んで食べるというものです。この手法は、どちらの参加者も結果として小さい方を受け取ったと主張できないため、公平であるとされています。

しかし、アリスの家では、ルールを決めるのは彼女であり、そのルールは決して公平ではありません。彼女は弟のボブに、1回ではなく $n$ 回のカットをするよう命じます。そして、それぞれのカットに対して、アリスはどちらか一方の側を選び、その側にあるケーキをすべて食べます。すべてのカットについて選び終えた後、残りをボブが食べることになります。

ケーキはデカルト平面上の正方形（実際には直方体ですが、すべてのカットは表面に対して垂直であると仮定します）として表され、その一辺の長さは $M$ です。ボブはちょうど $n$ 回のカットを行いました。今、アリスが選択を行う番です。アリスが賢明に選択した場合、彼女はどれだけのケーキを食べることができるでしょうか。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 500$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、2つの整数 $n$ ($1 \le n \le 4000$) と $M$ ($1 \le M \le 1000$) が含まれます。これらはカットの回数とケーキの一辺の長さを表します。ケーキは、対角線上の頂点が $(0, 0)$ と $(M, M)$ に位置する正方形です。

続く $n$ 行には、各カットを定義する3つの整数 $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$ を定義します。

より正確には、アリスには $n$ 個の直線の方程式が与えられます。各方程式について、彼女は $=$ 演算子を $\le$ または $\ge$ のいずれかに置き換える必要があり、それによって半平面の方程式が得られます。ケーキとこれら $n$ 個の半平面の共通部分が、アリスが食べることを許される領域となります。

各カットは、ケーキを面積がゼロではない2つの部分に分割します。

すべてのテストケースにおけるカットの総数は $10\,000$ を超えません。

出力

各テストケースについて、実数 $P$ ($0 \le P \le 100$) を小数点以下6桁で出力し、その後に '%' 記号を続けてください。これは、アリスがすべてのカットの側を最適に選択した場合に食べることができるケーキの割合を表します。あなたの出力した $P$ が正解の割合と $0.000002\%$ 以内の誤差であれば正解とみなされます。

入出力例

入力 1

1
2 1000
0 1 -750
1 0 -750

出力 1

93.750000%