## MAIN8_B - Overlapping Squares

you are given N (1<=N<=20000) squares on X-Y plane. Your task is to find the area which is common to all the squares (Area of intersection of all the squares)

### Input

First line contain T the number of test cases. then t test cases follow. First line of each test case contains N, the number of squares

Each of following N line contains 3 integer (X, Y, L) cordinate of lower left vertex and size of the square.

First line contain T the number of test cases. Then T test cases follow. First line of each test case contains N, the number of squares Each of following N line contains 3 integer (X, Y, L) cordinate of lower left vertex and size of the square.

-10^9<=X,Y<=10^9 1<=L<=10^9

### Output

For each test case print the answer in a new line.

### Example

Input:2 2 0 0 10 1 1 11 2 10 10 25 1 1 3Output:81 0

Added by: | Mahesh Chandra Sharma |

Date: | 2011-04-20 |

Time limit: | 0.442s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | Own problem used for NSIT-IIITA Main contest #8 |