Union of circles

Calculate the area covered by the union of circles.

Input

The first line provides the number of test cases, K (1 ≤ K ≤ 10).

For each test case, the first line specifies the number of circles, N (1 ≤ N ≤ 100). The following N lines each contain three integers: the coordinates of the circle's center and its radius, given as x_i y_i r_i. All coordinates are integers with absolute values not exceeding 1000, and the radius is a positive integer no greater than 1000.

Output

For each test case, output the area of the union of the circles, formatted to 6 decimal places.

Examples