Путешествие Джейна
Капитан Джейн хочет провести свой корабль "Вояжер" через поле астероидов, однако их имеется слишком большое количество для безопасной поездки. Чтобы помочь ему проложить путь, Вас попросили исследовать поле астероидов. Ваш план состоит в том, чтобы пролететь по полю и составить его план. Затем следует установить Ваш корабль с лазерной пушкой впереди таким образом, чтобы уничтожить как можно больше астероидов с помощью одного прямого выстрела лазерного луча.
Для простоты мы будем моделировать эту задачу в плоскости, где астероиды представлены кругами, лазерный луч является бесконечно тонким, а Ваш корабль можно установить где угодно и как угодно, внутри или снаружи астероидного поля.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 25). Каждый тест начинается с количества астероидов n (1 ≤ n ≤ 2000). Далее следует не более 5 тестов у которых n > 500. Каждая из следующих n строк содержит 3 действительных числа x_i, y_i, r_i означающих что астероид i имеет центр (x_i, y_i) и радиус r_i (-10^{6 }≤ x_i, y_i ≤ 10^6, 1 ≤ r_{i }≤ 100). Все значения заданы с точностью до двух десятичных знаков. Никакие два астероида не перекрываются и не пересекаются. Входные данные таковы, что ответ не изменится если радиусы астероидов изменить 10^{-6} в любом направлении.
Выходные данные
Для каждого теста вывести в отдельной строке наибольшее количество астероидов, которое можно уничтожить.