Лопання повітряних кульок
Джон захоплюється змаганнями з програмування. Проте є одна проблема: його команда не дуже вправна у програмуванні. Зазвичай це його не турбує, але його дратує, що всі отримують повітряні кульки за кожне правильне розв'язання. Команда Джона ніколи не отримує кульок, тоді як інші команди отримують одну за одною. Це його засмучує, тому Джон хоче, щоб усі інші команди теж залишилися без кульок.
Цього року у нього є план, як цього досягти. Джон найняв ніндзя, щоб той лопав усі кульки за нього. У будь-який момент під час змагання він може викликати ніндзя, який спуститься через отвір у стелі та лопне всі кульки, використовуючи свої сюрікени (зірочки ніндзя), а потім знову зникне через отвір у стелі. Звісно, ніндзя хоче використати якомога менше своїх цінних сюрікенів. Тому Джон повинен написати програму, яка обчислить, скільки сюрікенів потрібно, щоб лопнути всі кульки. Оскільки всі кульки зазвичай знаходяться приблизно на одній висоті, він може змоделювати проблему як 2-вимірну задачу. Він встановлює місце розташування ніндзя (де він з'являється) як початок координат (0, 0) і використовує кола для моделювання кульок. Щоб бути в безпеці, ці кола можуть мати різні радіуси. Припускається, що сюрікени кидаються з початку координат і рухаються по прямій лінії. Будь-яке коло/кулька, яке перетинає ця пряма, буде лопнуто цим сюрікеном. Питання тоді стає: скільки прямих ліній, що виходять з початку координат, потрібно, щоб перетнути всі кола?
Звісно, як згадувалося вище, Джон не дуже добрий програміст, тому він просить вас зробити цю програму для нього. Чи можете ви йому допомогти? Можливо, ви отримаєте кульку, якщо зробите це правильно...
Рисунок 1. Другий приклад
Вхідні дані
Перша строка вхідних даних містить одне число: кількість тестових випадків, які слідують. Кожен тестовий випадок має наступний формат:
Один рядок з одним цілим числом n (0 ≤ n ≤ 1,000): кількість кульок.
n рядків, кожен з яких містить три цілі числа x_i, y_i (-10^4 ≤ x_i, y_i ≤ 10^4), і r_i (1 ≤ r_i ≤ 10^4), що описують коло, яке використовується для моделювання i-ї кульки, де (x_i, y_i) - це центр кола, а r_i - радіус.
Ви можете припустити, що дві прямі (що виходять з початку координат), які є дотичними до двох різних кіл, утворюють кут не менше 10^{-6} радіанів у початку координат. Крім того, кола не перетинаються (але можуть торкатися) і не містять початок координат.
Вихідні дані
Для кожного тестового випадку у вхідних даних вихід повинен містити одне ціле число в одному рядку: мінімальну кількість сюрікенів, які ніндзя потребує, щоб лопнути всі кульки.