MAIN8_B - Overlapping Squares

no tags 

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

The first line contains 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 lines contain 3 integer (X, Y, L) coordinate 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 3

Output:
81
0

hide comments
Manik: 2015-05-21 17:41:33

Does anybody have a gun?

Last edit: 2015-05-21 17:43:38

Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8