Zapewne znasz schemat sprawiedliwego dzielenia tortu, w którym jedna osoba kroi tort na dwie części, a druga wybiera, którą z nich chce zjeść. Rozwiązanie to uznaje się za sprawiedliwe, ponieważ żaden z uczestników nie może twierdzić, że otrzymał mniejszą część.

Jednak u Alicji to ona dyktuje zasady – i z pewnością nie mają one być sprawiedliwe. Nakazuje swojemu młodszemu bratu, Bobowi, wykonanie $n$ cięć zamiast jednego. Teraz, dla każdego cięcia, Alicja wybiera jedną ze stron i zjada cały tort znajdujący się po tej stronie. Po tym, jak Alicja podejmie decyzje dla wszystkich cięć, Bob zjada resztę.

Tort jest reprezentowany jako kwadrat na płaszczyźnie kartezjańskiej (w rzeczywistości jest to prostopadłościan, ale zakładamy, że wszystkie cięcia są prostopadłe do powierzchni) o długości boku $M$. Bob właśnie wykonał $n$ cięć i teraz nadszedł czas, aby Alicja dokonała swoich wyborów. Określ, ile tortu będzie mogła zjeść, jeśli dokona optymalnych wyborów.

Wejście

Pierwsza linia wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 500$). Następnie następują opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $n$ ($1 \le n \le 4000$) oraz $M$ ($1 \le M \le 1000$) – liczbę cięć oraz długość boku tortu. Tort jest kwadratem o przeciwległych wierzchołkach znajdujących się w punktach $(0, 0)$ oraz $(M, M)$.

Następnie następuje $n$ linii, z których $i$-ta zawiera trzy liczby całkowite $A_i$, $B_i$ oraz $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$), które definiują równanie prostej $A_ix + B_iy + C_i = 0$ dla $i$-tego cięcia.

Mówiąc dokładniej, Alicja otrzymuje zbiór $n$ równań prostych. Dla każdego równania musi zastąpić operator $=$ operatorem $\le$ lub $\ge$, otrzymując równanie półpłaszczyzny. Część wspólna tortu z sumą $n$ takich półpłaszczyzn jest tym, co Alicja będzie mogła zjeść.

Każde cięcie dzieli tort na dwie części o niezerowym polu.

Całkowita liczba cięć we wszystkich przypadkach testowych nie przekracza $10\,000$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczą linię zawierającą liczbę rzeczywistą $P$ ($0 \le P \le 100$) z 6 miejscami po przecinku, po której następuje znak „%” – procent tortu, który Alicja będzie mogła zjeść, jeśli wybierze strony wszystkich cięć optymalnie. Twoje rozwiązanie zostanie zaakceptowane, jeśli $P$ różni się od poprawnego wyniku o nie więcej niż $0{,}000002\%$.

Przykład

Wejście 1

1
2 1000
0 1 -750
1 0 -750

Wyjście 1

93.750000%