Подорож Джейн
Капітан Джейн прагне провести свій корабель "Вояжер" через поле астероїдів, але їх занадто багато для безпечного проходу. Щоб допомогти йому прокласти шлях, вас попросили дослідити поле астероїдів. Ваш план полягає в тому, щоб пролетіти через поле і скласти його карту. Потім потрібно розмістити ваш корабель з лазерною гарматою так, щоб знищити якомога більше астероїдів одним прямим пострілом лазерного променя.
Для спрощення ми будемо моделювати це завдання на площині, де астероїди представлені колами, лазерний промінь є нескінченно тонким, а ваш корабель можна розмістити будь-де і в будь-якому напрямку, як всередині, так і зовні поля астероїдів.
Вхідні дані
Перший рядок містить кількість тестів 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} в будь-якому напрямку.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найбільшу кількість астероїдів, які можна знищити.