На лесной опушке растет дружная семейка грибов. Местоположение каждого гриба задается координатами x, y, а шляпка гриба имеет радиус r. Когда идет дождь, радиус шляпки каждого гриба увеличивается cо скоростью 1 сантиметр в минуту. Когда дождь заканчивается (а он идет не более t минут), шляпки прекращают расти. Если во время дождя шляпки двух грибов соприкоснулись, то они немедленно перестают расти, чтобы не навредить друг другу. Грибы очень дружные, поэтому если перестают расти два гриба, то и все остальные тоже не растут.

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

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

Первая строка содержит количество тестов n. Первая строка каждого теста содержит два целых числа: количество грибов k (k ≤ 10) и длительность дождя t (t ≤ 100). Следующие k строк содержат описание грибов: координаты x и y (x ≤ 100, y ≤ 100) и радиус шляпки r (r ≤ 10). Координаты и радиус даны в сантиметрах.

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

Для каждого теста вывести одно число – величину, на которую увеличится радиус всех грибов. Результат не должен содержать незначащих нулей и должен быть выведен с точностью до двух знаков после запятой.