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.

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