Подорож Джейн#6970
Капітан Джейн прагне провести свій корабель "Вояжер" через поле астероїдів, але їх занадто багато для безпечного проходу. Щоб допомогти йому прокласти шлях, вас попросили дослідити поле астероїдів. Ваш план полягає в тому, щоб пролетіти через поле і скласти його карту. Потім потрібно розмістити ваш корабель з лазерною гарматою так, щоб знищити якомога більше астероїдів одним прямим пострілом лазерного променя.
Для спрощення ми будемо моделювати це завдання на площині, де астероїди представлені колами, лазерний промінь є нескінченно тонким, а ваш корабель можна розмістити будь-де і в будь-якому напрямку, як всередині, так і зовні поля астероїдів.
Перший рядок містить кількість тестів (1 \leq t \leq 25). Кожен тест починається з кількості астероїдів (1 \leq n \leq 2000). Не більше ніж у тестах n > 500. Кожен з наступних рядків містить дійсних числа x_i, y_i, r_i, що означають, що астероїд має центр (x_i, y_i) і радіус r_i (-10^{6} \leq x_i, y_i \leq 10^6, 1 \leq r_i \leq 100). Усі значення задані з точністю до двох десяткових знаків. Жодні два астероїди не перекриваються і не перетинаються. Вхідні дані такі, що відповідь не зміниться, якщо радіуси астероїдів змінити на 10^{-6} в будь-якому напрямку.
Для кожного тесту виведіть в окремому рядку найбільшу кількість астероїдів, які можна знищити.
Приклад 1