Janeway's Journey

Captain Janeway wants to take Voyager through an asteroid field, but there are too many asteroids for the trip to be safe. To blaze a path, you fly a shuttle into the field. The plan is to cross the field and note how the asteroids are laid out, then park the shuttle in the position and orientation that lets a single straight phaser blast destroy as many asteroids as possible.

To keep the problem simple, everything happens in the plane. Asteroids are circles, the phaser beam is an infinitely thin line, and you may place the shuttle anywhere you like, inside or outside the field, pointing in any direction.

The first line contains one integer $T$ ($1 \le T \le 25$), the number of test cases.

The first line of each test case contains one integer $N$ ($1 \le N \le 2000$), the number of asteroids. At most 5 test cases have $N > 500$. Each of the next $N$ lines contains three space separated real numbers $x_i$, $y_i$, $r_i$, meaning that asteroid $i$ is centered at $(x_i, y_i)$ and has radius $r_i$. Here $-10^6 \le x_i, y_i \le 10^6$ and $1 \le r_i \le 100$, and all three values are given to two decimal places.

No two asteroids overlap or intersect. The input is such that the answer stays the same even if every radius grows or shrinks by $10^{-6}$.

For each test case, print one line with the maximum number of asteroids that can be destroyed.