lattice-2

There are $N$ sprinklers in the garden. The sprinklers are given by their coordinates ($x_k,y_k~~k=1,\ldots,N$). Additionally, for each sprinkler, the watering distance $r_k$ is given ($k=1,\ldots,N$). This should be understood as: a sprinkler at $(x, y)$ with radius $r$ reaches every point $(X, Y)$ in the garden such that $max(|x − X|, |y − Y|) ≤ r$. For example, a sprinkler at $(1, 7)$ with r=3 reaches all points in the rectangle $[−2, 4] × [4, 10]$. What is the total watered area ($A$)?

Input specification

The first line contains $T$ - the number of test cases. Then $T$ test case descriptions follow. For each test case: First line: $N$, the number of sprinklers. Then $N$ lines follow, each containing three numbers $x_k~~ y_k~~ r_k~~(k=1,\ldots,N)$.

Output specification

Output $T$ lines, each containing the requested area $A$.

Constraints

$1\le T \le 100$
$1\le N \le 22$
$-1\_000\_000\le x_k \le 1\_000\_000$
$-1\_000\_000\le y_k \le 1\_000\_000$
$1\le r_k \le 1\_000\_000$
Partial points can be earned by solving problem instances with constraints $−1000 ≤ x_k, y_k, r_k ≤ 1000~~~(k=1,\ldots,N)$.

Sample input 1

1. 6
2. 1
3. 0 0 1
4. 2
5. 0 0 1
6. 10 0 1
7. 3
8. 0 0 1
9. 10 0 1
10. 100 0 1
11. 5
12. 0 0 1
13. 0 0 2
14. 0 0 3
15. 0 0 4
16. 0 0 5
17. 2
18. 0 0 2
19. 1 1 2
20. 3
21. 0 0 5
22. 5 -2 3
23. 5 2 3

Sample output 1

1. 4
2. 8
3. 12
4. 100
5. 23
6. 130