Puddles

Calculate the total area covered by n circular puddles.

Input

The first line of the input file specifies the number of test cases K (1 ≤ K ≤ 100).

For each test case, the first line contains an integer n (1 ≤ n ≤ 100), representing the number of puddles. The next n lines provide the coordinates of the center and the radius of each puddle in the format x_i y_i r_i. All numbers are guaranteed to be integers and do not exceed 1000 in absolute value. The radius is always positive.

Output

For each test case, output a single real number with eight decimal places, representing the total area covered by the puddles.

Examples