lattice-2

Van $N$ locsoló a kertben. A locsolók koordinátáikkal adottak ($x_k,y_k~~k=1,\ldots,N$). Adott még ezenkívül minden locsoló esetén a belocsolt táv ($r_k~~k=1,\ldots,N$). Ezt úgy kell érteni, hogy egy $x,y$ ban levő és $r$ sugarú locsoló minden olyan $X,Y$ pontot elér a kertben melyre $max(|x-X|,|y-Y|)\le r$. Például egy $(1,7)$-ban levő és $r=3$ sugarú locsoló eléri a $[-2,4]\times [4,10]$ téglalap összes pontját. Mekkora a belocsolt terület ($A$)?

Bemenet specifikáció

Az első sorban $T$ - az esetek száma. Ezután $T$ eset leírása következik. Egy eset első sorában van a locsolók $N$ száma, majd $N$ sor következik az $x_k~~ y_k~~ r_k~~(k=1,\ldots,N)$ számokkal. Feltehető hogy nincsen két locsoló ugyanazon a helyen és és nincsen olyan pont a kertben melyet 5-nél több locsoló is elér.

Kimenet specifikáció

$T$ sor, mindegyikben a keresett $A$ szám.

Korlátok

$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$
Részpont szerezhető a $-1000\le x_k,y_k,r_k\le 1000~~~(k=1,\ldots,N)$ korlátokkal rendelkező feladat-példányok megoldására.

1. példa bemenet

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

1. példa kimenet

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