Description

不知道你有没有注意到，在东 14# 后面有一块工地，工地里有很多起重机，这些起重机要协同工作。现在，我们假设它们的高度都一样，由于起重机的悬臂要在空中旋转，所以两部起重机不能靠得太近，否则就会发生事故。

如何部署起重机一直是个难题。现在，校长要你来部署这些起重机，使它们能安全运转（当且仅当悬臂无论怎么旋转都无法碰撞），并且要使它们覆盖的面积和最大。每部起重机都可覆盖以它为圆心，半径为r的圆形区域。那么，你能完成这个任务吗？

Input

输入的第一行包含一个整数c，表示测试数据的组数。 每组数据的第一行包含一个整数n表示要备用的起重机的数目（1 <= n <= 15）。 接下来n行，每行包含三个整数：x，y，r。其中x和y表示可以布置起重机的位置的坐标（-1000 <= x, y <= 1000），r表示布置在该位置的起重机的覆盖半径（1 <= r <= 1000）。

Output

对每组数据，输出一个整数A，表示最大的覆盖面积为 Aπ ，每组数据占一行。

Sample

Input

1
3
0 0 4
5 0 4
-5 0 4

Output

32

Hint

注意相切时不合法！

Source: ycc