Cranes

A crane is a great tool for putting up a building, and using several cranes makes construction go even faster. But when too many cranes work on the same building they can become dangerous: as a crane spins around it can bump into another crane and topple over, causing serious damage. Safety rules therefore require the cranes to be spaced far enough apart that no part of one crane can ever touch any part of another crane.

The construction site is a square grid, and several grid points are marked as possible crane locations. A crane placed at a location has an arm of length $r$ that rotates around that location, so it covers every point within distance $r$ of the location (a disk of radius $r$). Two placed cranes are allowed together only if their disks never touch, that is, the distance between their locations is strictly greater than the sum of their arm lengths.

Respecting the safety rule, choose which of the marked locations to place cranes on so that the total area covered by all the placed cranes is as large as possible.

The first line contains an integer $T$, the number of test cases. Each test case starts with a line containing an integer $C$, the number of possible crane locations, with $C \le 15$. Each of the next $C$ lines contains three integers $x$, $y$, and $r$, each between $-10000$ and $10000$ inclusive: $(x, y)$ are the grid coordinates of the location and $r$ is the arm length of the crane that can be placed there.

For each test case, let $A$ be the maximum total area that can be covered while respecting the safety rule. Output one line with the integer $B$ such that $A = B \times \pi$. Because a crane covers an area of $\pi r^2$ and the placed disks never overlap, $B$ equals the largest possible sum of $r^2$ over a set of cranes chosen so that none of them touch.