크레인

크레인은 건물을 세우는 데 아주 유용한 장비이며, 크레인을 여러 대 사용하면 공사를 훨씬 빠르게 진행할 수 있다. 하지만 같은 건물에서 너무 많은 크레인이 작업하면 위험할 수 있다. 크레인이 회전하다가 다른 크레인과 부딪히면 넘어져 큰 피해가 발생할 수 있기 때문이다. 그래서 안전 규정은 어떤 크레인의 어떤 부분도 다른 크레인의 어떤 부분과 닿을 수 없을 만큼 크레인들을 충분히 떨어뜨려 배치하도록 요구한다.

공사장은 정사각형 격자이며, 격자 위의 몇몇 지점이 크레인을 놓을 수 있는 후보 위치로 표시되어 있다. 어떤 위치에 놓인 크레인은 길이가 $r$인 팔이 그 위치를 중심으로 회전하므로, 그 위치로부터 거리가 $r$ 이하인 모든 점(반지름 $r$의 원판)을 덮는다. 두 크레인을 함께 놓을 수 있으려면 두 원판이 서로 닿지 않아야 한다. 즉, 두 위치 사이의 거리가 두 팔 길이의 합보다 반드시 커야 한다.

안전 규정을 지키면서 표시된 위치들 중 크레인을 놓을 곳을 골라, 놓인 크레인들이 덮는 전체 넓이를 최대로 만들어라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 크레인을 놓을 수 있는 후보 위치의 수 $C$가 주어지며, $C \le 15$이다. 이어지는 $C$개의 줄에는 각각 세 정수 $x$, $y$, $r$가 주어진다. 세 값은 모두 $-10000$ 이상 $10000$ 이하이며, $(x, y)$는 위치의 격자 좌표, $r$는 그 위치에 놓을 수 있는 크레인의 팔 길이이다.

각 테스트 케이스마다, 안전 규정을 지키면서 덮을 수 있는 최대 넓이를 $A$라 할 때, $A = B \times \pi$를 만족하는 정수 $B$를 한 줄에 출력한다. 크레인 하나가 덮는 넓이는 $\pi r^2$이고 놓인 원판들은 서로 겹치지 않으므로, $B$는 서로 닿지 않게 고른 크레인들의 $r^2$ 합의 최댓값과 같다.