Popping Balloons#3123

Popping Balloons

2 seconds

32 megabytes

Hard

John loves programming contests. There is just one problem: his team is not very good at programming. This usually does not bother him, but what does bother him is that everyone gets a balloon for every correct submission. John’s team never gets any balloons, while other teams get one balloon after another. This frustrates him, so John would like to see that other teams also have no balloons.

This year, he has come up with a plan. John hired a ninja to pop all balloons for him. At any time during the contest, he can call for the ninja to come down through a hole in the ceiling, use his shurikens (ninja stars) to pop all balloons, and leave again through the hole. Of course, the ninja wants to use as few of his precious shurikens as possible. Therefore, John must write a program that computes how many shurikens are needed to pop all balloons. Because all balloons are usually at approximately the same height, he can model the problem as a $2$ -dimensional problem. He sets the location where the ninja appears as the origin $(0, 0)$ and uses circles to model the balloons. To be safe, these circles can have different radii. Shurikens are thrown from the origin and move in a straight line. Any circle/balloon crossed by this line will be popped by the shuriken. The question is: how many lines passing through the origin are needed to cross all circles?

As mentioned above, John is not a very good programmer, so he asks you to write this program for him. Can you help him out? You might get a balloon if you get it right...

Figure 1. Second sample case

Input

The first line of the input contains a single integer: the number of test cases to follow. Each test case has the following format:

A line with a single integer $n$ ( $0 \leq n \leq 1000$ 0 \le n \le 1\,000): the number of balloons.
$n$ lines, each containing three integers $x_{i}$ x_i, $y_{i}$ y_i ( $- 1 0^{4} \leq x_{i}, y_{i} \leq 1 0^{4}$ -10^4 \le x_i, y_i \le 10^4), and $r_{i}$ r_i ( $1 \leq r_{i} \leq 1 0^{4}$ 1 \le r_i \le 10^4), describing the $i$ -th balloon as a circle centered at $(x_{i}, y_{i})$ (x_i, y_i) with radius $r_{i}$ r_i.

You can assume that two lines (rooted at the origin) that are tangent to two distinct circles make an angle of at least $1 0^{- 6}$ 10^{-6} radians at the origin. Furthermore, no two circles intersect (but they may touch), and no circle contains the origin.

Output

For each test case, print a single integer: the minimum number of shurikens the ninja needs to pop all balloons.

Examples

Example 1