400968: GYM100298 A Atlantis

21 December 2012, 21:13 (GMT-2), The Archipelago of the Azores.

Crustal movements bring to the surface a never-before-seen island filled with exceptionally preserved pieces of ancient architecture. Exploration of this wonder is pending due to tons of sea water still covering the island.

Its topology consists of multiple cylindrical elevations and depressions. You can view it as a set of platforms of varying height. Circles, which are the cylinders' bases, may enclose each other, but their rims never touch.

Atlantis was built from highly waterproof material. Thus, the water cannot escape the depressed cylinders. Drilling through this priceless remnant of a civilization long gone is out of the question. Pumps will be used instead. Water removal will cost 1 / π per cubic meter.

Your mundane task is to calculate the total cost of this endeavor.

First line contains the number of test cases. Each of the test cases adheres to the following specification.

The first number in a test case is n (0 ≤ n ≤ 150000) – the number of cylinders. Each of the next n lines contain four natural numbers x_i, y_i, r_i, h_i ( - 10⁶ ≤ x_i, y_i ≤ 10⁶;0 < r_i ≤ 10⁶; - 100 ≤ h_i ≤ 100;h_i ≠ 0) – center of the i-th cylinder, its radius and the height of its interior relative to its exterior (all given in meters).

For each test case, output, in a single line, the cost of removing the remaining water from Atlantis.

2
3
0 0 10 3
3 3 2 -1
-1 -2 1 -1
5
0 0 9 -2
2 2 2 1
-3 1 3 1
-2 0 1 2
3 -3 2 3

5
140