COVER2 - 3D Cover

In the 3D Cartesian coordinate system, there are n cubes. These cubes are all axis-paralleled. What's the volume of the union of these cubes?

Input

There is a single integer m in the very first line of the input, the number of test cases. m blocks follow.

For each test, the first line contains a single integer n (1<=n<=100), the number of cubes. n lines follow, each contains four integers x, y, z, r (-1000 <= x, y, z <=1000,1 <= r <= 200), separated by spaces. x, y, z are the X, Y, Z coordinates of the center of the cube, and r is the distance between the center and any surface of the cube.

Output

m lines, each contains a single integer - the answer.

Example

Sample Input:
1
3
0 0 0 3
1 -1 0 1
19 3 5 6

Sample Output:
1944

Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 1997,Day 2; description by Blue Mary

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.