Problem Statement

In $xyz$-space, you are given a sphere $A$ of radius $R_A$ centered at $(X_A, Y_A, Z_A)$ and a sphere $B$ of radius $R_B$ centered at $(X_B, Y_B, Z_B)$.

Find the volume of the intersection of $A$ and $B$.

Solve $T$ test cases.

Input

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

$\text{case}_i$ represents the $i$-th test case and is given in the following format:

$X_A\ Y_A\ Z_A\ R_A$
$X_B\ Y_B\ Z_B\ R_B$

• $1\leq T\leq 10^5$
• $|X_A|,|Y_A|,|Z_A|,|X_B|,|Y_B|,|Z_B|\leq 10^6$
• $1\leq R_A, R_B\leq 10^6$
• All input values are integers.

Output

For each test case, output the answer on one line. Your answer is considered correct if its relative error or absolute error from the judge's answer is at most $10^{-6}$. The judge's answer is guaranteed to have an absolute error or relative error of at most $10^{-15}$ from the true value. Print a newline at the end.

Sample

4
1 1 1 1
2 1 1 1
3 -4 5 2
-6 1 8 3
10 -7 4 8
12 -6 5 2
-5 8 -3 5
1 4 2 4

1.30899693899574718269276807636645953508215391640629409207289358012825683595258708276168118
0
33.510321638291127876934862754981364098103140260001128757066075651283375000386229318699038
0.350444254990991599437706458856313749083937801369436963178239367089864899250352524244104371