Mines

There are $N$ mines buried in an old battlefield. Each mine affects an axis-parallel square area determined by its performance. Treat the mine's location as the center of that square area. When a mine explodes, every mine whose center lies inside the exploding square area also explodes. By chain reaction, the mines inside the square areas of those newly exploded mines explode as well.

A mine lying exactly on the boundary of an exploding square area also explodes. In the figure below, if mine 4 is triggered first, mines 3 and 6 explode. If mine 1 is triggered first, mine 4 explodes, and the following blast makes mines 3 and 6 explode too. Therefore, triggering mines 1, 2, and 5 causes every mine to explode.

Given $N$ mines on a two-dimensional plane, each with its explosion performance described as a square area, write a program that finds the minimum number of mines you must trigger directly so that all mines explode.

The input is read from standard input. It consists of $T$ test cases. The first line contains the number of test cases $T$. Each test case begins with a line containing the number of mines $N$ ($3 \le N \le 2\,000$). Each of the next $N$ lines contains three integers $x$, $y$, and $d$, where $x$ and $y$ are the coordinates of the mine and $d$ is the side length of the square that represents its explosion performance ($1 \le x, y \le 10\,000\,000$, $1 \le d \le 1\,000\,000$). Since the square is centered at $(x, y)$ with side length $d$, the distance from the center to each side is $d/2$.

Write the result to standard output. For each test case, print exactly one line containing the minimum number of mines that must be triggered directly so that all mines explode.