Лопание шариков
Джон обожает участвовать в соревнованиях по программированию. Однако его команда не слишком сильна в программировании. Обычно это его не беспокоит, но его расстраивает, что за каждое правильно решенное задание команды получают шарики. Команда Джона никогда не получает шариков, в то время как другие команды получают их один за другим. Это его огорчает, и Джон хочет, чтобы у других команд тоже не было шариков.
В этом году у него есть план, как этого добиться. Джон нанял ниндзя, который будет лопать все шарики за него. В любой момент соревнования он может вызвать ниндзя, который спустится через отверстие в потолке и лопнет все шарики с помощью своих сюрикенов (звездочек ниндзя), а затем снова исчезнет через отверстие в потолке. Конечно, ниндзя хочет использовать как можно меньше своих драгоценных сюрикенов. Поэтому Джон должен написать программу, которая вычисляет, сколько сюрикенов потребуется, чтобы лопнуть все шарики. Поскольку все шарики обычно находятся примерно на одной высоте, он может смоделировать задачу как 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} радиан в начале координат. Кроме того, круги не пересекаются (но могут касаться) и не содержат начало координат.
Выходные данные
Для каждого теста во входных данных вывод должен содержать одно целое число в одной строке: минимальное количество сюрикенов, которое нужно ниндзя, чтобы лопнуть все шарики.