Вы наверняка знакомы с честной схемой разрезания торта, когда один человек разрезает торт пополам, а другой выбирает, какую часть он предпочитает есть. Это решение считается справедливым, так как ни один из участников не может претендовать на то, что в результате получил меньшую часть.

Что ж, Алиса диктует правила, и уж точно они не должны быть справедливыми. Она приказывает своему младшему брату Бобу сделать n разрезов, а не один. Теперь для каждого разреза Алиса выбирает одну из сторон и съедает весь торт с этой стороны. После того как она закончит разрезание, Боб съедает остальное.

Торт изображается в виде квадрата на декартовой плоскости (на самом деле это, конечно, прямоугольный параллелепипед, но мы предполагаем, что все разрезы перпендикулярны поверхности) с длиной стороны m. Боб только что сделал n разрезов, и теперь пришло время Алисе сделать свой выбор. Определите, сколько торта она сможет съесть, если сделает правильный выбор.

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 500). Далее следуют описания тестов.

Первая строка каждого набора входных данных содержит два целых числа n (1 ≤ n ≤ 4000) и m (1 ≤ m ≤ 1000) - количество разрезов и длина стороны торта. Торт представляет собой квадрат, противоположные вершины которого расположены в точках (0, 0) и (m, m).

Затем следуют n строк, i-я из которых содержит три целых числа ai, bi и ci (-1000 ≤ ai, bi ≤ 1000, -106 ≤ ci ≤ 106, ai^2 + bi^2 > 0), которые определяют линейное уравнение aix + biy + ci = 0 i-го разреза.

Точнее, Алисе дается набор из n линейных уравнений. Для каждого уравнения ей нужно заменить оператор = на ≤ или ≥, получив уравнение полуплоскости. Пересечение пирога с суммой n таких полуплоскостей - это то, что Алисе будет разрешено съесть.

Каждый разрез делит торт на две части ненулевой площади каждая.

Общее количество разрезов во всех тестах не превышает 10 000.

Выходные данные

Для каждого теста выведите одну строку, содержащую вещественное число p (0 ≤ p ≤ 100) с 6 десятичными цифрами, за которым следует символ % - процент торта, который Алиса сможет съесть, если оптимально выберет все стороны разрезов. Ваше решение будет принято, если p отличается от правильного процента не более чем на 0.000002%.