When walking on the remote isle of Foula,
professor Oak was dive-bombed
by many bonxies that were protecting their territories.
Those (fortunately, failed) attacks inspired this problem.

Assume an infinite flat world.
There, we have n bonxies,
each protecting a disc of radius r_{i} centered at (x_{i}, y_{i}).
Please compute a point protected by the maximum number of bonxies.

Input

Input is all integer numbers,
and consists of several cases,
each one with n
followed by the n triples x_{i} y_{i} r_{i}.
You can assume 1 ≤ n ≤ 1000,
that all coordinates are at most 10^{9} in absolute value,
that all radii are between 1 and 10^{9},
that each pair of circles of the discs either do not intersect,
or intersect at exactly two points,
and that there is no point in the plane with more than two circles on it.
The input cases have no precision issues.

Output

For every case, print the maximum number of bonxies that can protect a point.

Hint

The expected solution has cost Θ(n^{2} logn).

Public test cases

**Input**

5 0 0 5 0 -6 2 2 0 2 -1 1 3 9 9 1 2 1000000000 -1000000000 1000000000 500000000 -500000000 42

**Output**

3 2

Information

- Author
- Ivan Geffner
- Language
- English
- Official solutions
- C++
- User solutions
- Event
- Setzè Concurs de Programació de la UPC - Final
- Date
- 2018-09-19