Seguramente estás familiarizado con el esquema de corte de pastel justo, donde una persona corta el pastel en dos y la otra persona elige qué parte prefiere comer. Se supone que esta solución es justa, ya que ninguno de los participantes puede afirmar haber recibido la parte más pequeña como resultado.

Bueno, en casa de Alice, es ella quien dicta las reglas, y ciertamente no se supone que sean justas. Ella le ordena a su hermano menor, Bob, que haga $n$ cortes en lugar de uno. Ahora, para cada corte, Alice elige uno de los lados y come todo el pastel de ese lado. Después de que ella termina de pasar por todos los cortes, Bob recibe el resto.

El pastel está representado como un cuadrado en el plano cartesiano (en realidad es un cuboide, por supuesto, pero asumimos que todos los cortes son perpendiculares a la superficie) con una longitud de lado $M$. Bob acaba de hacer $n$ cortes y ahora es el momento de que Alice tome sus decisiones. Determina cuánto pastel podrá comer si elige sabiamente.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 500$). Siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ ($1 \le n \le 4000$) y $M$ ($1 \le M \le 1000$): el número de cortes y la longitud del lado del pastel. El pastel es un cuadrado con sus vértices opuestos ubicados en los puntos $(0, 0)$ y $(M, M)$.

Luego siguen $n$ líneas, la $i$-ésima de ellas contiene tres enteros $A_i$, $B_i$ y $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$), que definen la ecuación de la línea $A_ix + B_iy + C_i = 0$ del $i$-ésimo corte.

Más precisamente, a Alice se le da un conjunto de $n$ ecuaciones de línea. Para cada ecuación, ella necesita reemplazar el operador $=$ con $\le$ o $\ge$, obteniendo una ecuación de semiplano. La intersección del pastel con la suma de $n$ tales semiplanos es lo que a Alice se le permitirá comer.

Cada corte divide el pastel en dos partes de área distinta de cero.

El número total de cortes en todos los casos de prueba no supera los $10\,000$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un número real $P$ ($0 \le P \le 100$) con 6 decimales, seguido del signo '%': el porcentaje del pastel que Alice podrá comer si elige todos los lados de los cortes de manera óptima. Tu solución será aceptada si $P$ difiere del porcentaje correcto por no más de $0.000002\%$.

Ejemplos

Entrada 1

1
2 1000
0 1 -750
1 0 -750

Salida 1

93.750000%