Puddles

Input

The first line contains the number of test cases $K$ (1 \leq K \leq 100).

For each test case, the first line contains an integer $n$ (1 \leq n \leq 100) — 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 integers and their absolute value does not exceed $1000$. The radius is always positive.

Output

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

Examples