eolymp
bolt
Try our new interface for solving problems
Problems

Janeway`s Journey

Janeway`s Journey

Time limit 75 seconds
Memory limit 64 MiB

Captain Janeway wants to take the Voyager through an asteroid field, but there are too many asteroids for such a trip to be safe. To help blaze a path, you have been asked to take a shuttle into the asteroid field. Your plan is to fly through the field and note its layout, then position the shuttle in such a manner to take out as many asteroids as possible with a single, straight-line phaser blast.

For simplicity we will model this problem in the plane, with circular asteroids, an infinitely thin phaser, and the ability to position your shuttle wherever and however you like, in or around the asteroid field.

Input data

Starts with a line that contains the number of test cases t (1 t 25). Each test case begins with a line with a single integer n (1 n 2000) denoting the number of asteroids. Furthermore, there will be at most 5 test cases for which n > 500. This line is followed by n lines each with 3 space-separated real numbers x_i, y_i, r_i which specify that asteroid i is centered at (x_i, y_i) and has radius r_i (-10^{6 }x_i, y_i10^6, 1 r_{i }100). All of these numbers will be given to two decimal places. No asteroids will overlap or intersect each other. The input will be such that the answer will not change even if the radii of the asteroids vary by 10^{-6} in either direction.

Output data

For each test case, print a single integer on its own line denoting the maximum number of asteroids that may be destroyed.

Examples

Input example #1
1
3
0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00
Output example #1
2
Source 2013 North America - Pacific Northwest Region Programming Contest, Problem J