공정한 케이크 자르기 방식에 대해서는 잘 알고 있을 것입니다. 한 사람이 케이크를 두 조각으로 자르면, 다른 사람이 원하는 조각을 선택해서 가져가는 방식입니다. 이 방식은 어느 쪽도 더 작은 조각을 받았다고 주장할 수 없으므로 공정하다고 여겨집니다.

하지만 앨리스의 집에서는 규칙을 정하는 사람이 앨리스이며, 이 규칙은 결코 공정하지 않습니다. 앨리스는 남동생 밥에게 한 번이 아니라 $n$번의 자르기를 시키기로 합니다. 이제 모든 자르기에 대해 앨리스는 한쪽 면을 선택하여 그쪽의 케이크를 모두 먹습니다. 앨리스가 모든 자르기에 대한 선택을 마치면, 밥은 남은 케이크를 먹습니다.

케이크는 데카르트 평면 위의 정사각형으로 표현됩니다(물론 실제로는 직육면체이지만, 모든 자르기는 표면에 수직이라고 가정합니다). 케이크의 한 변의 길이는 $M$입니다. 밥은 방금 $n$번의 자르기를 마쳤고, 이제 앨리스가 선택을 할 차례입니다. 앨리스가 현명하게 선택한다면 얼마나 많은 케이크를 먹을 수 있을지 결정하십시오.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 $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$을 정의합니다.

더 정확히 말하면, 앨리스에게는 $n$개의 직선 방정식이 주어집니다. 각 방정식에 대해 앨리스는 $=$ 연산자를 $\le$ 또는 $\ge$ 중 하나로 바꾸어 반평면 방정식을 얻어야 합니다. 케이크와 $n$개의 반평면의 교집합이 앨리스가 먹을 수 있는 부분이 됩니다.

각 자르기는 케이크를 0이 아닌 넓이를 가진 두 부분으로 나눕니다.

모든 테스트 케이스의 총 자르기 횟수는 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%