Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3500
Electron Cloud

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The electron is described in terms of its probability distribution or probability density. This probability distribution does not have definite cutoff points; its edges are somewhat fuzzy. Hence the term "electron cloud." This cloudy probability distribution takes on different shapes, depending on the state of the atom.

In order to describe a nuclear action, you are asked to tell where the electrons may occur.

Here we assume that the electrons only occur within a sphere whose location and radius are given. The action consists of only two atoms.

Input

There are multiple test cases. The first line of input is an integer T indicating the number of test cases. (0 < T ≤ 50)

Each test case consists of a line containing 8 integers X1, Y1, Z1, R1, X2, Y2, Z2 and R2, describing the coordinates and the radiuses of the two atoms. The absolute value of each coordinate do not exceed 100 and 0 < R1, R2 ≤ 100.

Output

For each test case, output the volume of space where the electrons may occur, accurated to the nearest 0.01.

Sample Input

3
0 0 0 1 0 0 2 1
0 0 0 2 0 0 2 2
0 0 0 2 0 0 2 1


Sample Output

8.38
56.55
36.00


References

Author: GUAN, Yao
Submit    Status