## 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

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

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 |