Cosmic Cleaner

소행성 $n$개가 소행성대를 이루고 있다. 이 소행성들은 중력 때문에 행성 주위를 공전하며, 현재 소행성과 행성은 서로 충돌하지 않는다. 청소부에게 행성을 없애라는 명령이 내려졌다. 청소부는 첨단 기술로 행성을 소멸시키며, 행성 중심에 가까운 것은 무엇이든 즉시 지워진다. 천체를 완전한 구로 볼 때, 임무를 수행한 뒤 소행성에 속하지만 청소되는 영역의 총 부피를 구할 수 있는가?

천체들은 서로 교차하지 않는다. 다시 말해 두 천체가 공유하는 점은 없다.

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 수 $T$가 주어진다. 이어서 모든 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 정수 $n$이 주어진다.

다음 $n$개 줄에는 각각 네 정수 $x$, $y$, $z$, $r$이 주어지며, 이는 중심이 $(x, y, z)$이고 반지름이 $r$인 소행성을 나타낸다.

마지막 줄에는 네 정수 $x'$, $y'$, $z'$, $r'$이 주어진다. 이는 청소 영역의 중심이기도 한 행성의 중심이 $(x', y', z')$에 있고, 청소부의 영향이 미치는 영역의 반지름이 행성의 반지름보다 큰 $r'$임을 나타낸다.

각 테스트 케이스마다 한 줄에 “Case #x: y”를 출력한다(따옴표 제외). $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 이 테스트 케이스의 답이며 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다.

형식적으로, 답이 $a$이고 출제진의 답이 $b$일 때 $|a-b|/\max\{1,|b|\} \le 10^{-6}$이면 정답으로 인정된다.

• $1 \le T \le 6000$
• $1 \le n \le 100$
• $-10^3 \le x, y, z, x', y', z' \le 10^3$
• $1 \le r, r' \le 10^3$

다음 그림은 예제 테스트 케이스를 나타낸다. 영향 영역은 빨간 구 안쪽이고, 소행성은 예제에 나온 순서대로 주황, 파랑, 초록으로 칠해져 있다.