Dolphin Pool

Time limit1sMemory limit128 MB

Summary

Given up to 20 circles with disjoint centers, count the bounded regions outside all circles that the circles enclose.

Level: Medium6 of 10
Topics: Geometry, Graph, DFS
Solved: No attempts yet

Problem

In a newly built dolphin pool on Kish Island in the Persian Gulf, one of the fun games is the following. The host throws several plastic rings (circles) onto the water so that no ring's center lies inside any other ring, and no two rings are tangent to each other. On the host's whistle, the dolphins are trained to jump out through the closed areas that lie completely outside every ring, one dolphin per such area. The dolphins jump out if and only if the number of such closed areas is exactly equal to the number of dolphins.

Here, a closed area is a bounded region of the plane that lies outside all of the rings and is enclosed by them. Given the position and radius of every ring, write a program that computes the number of closed areas formed between the rings.

Input

The first line contains the number of test cases (at most 20). The first line of each test case contains an integer $N$ ( $1 \le N \le 20$ ), the number of plastic rings. Each of the following $N$ lines contains three integers: the first two are the $x$ and $y$ coordinates of the center of the ring's circle, and the third is its radius. Coordinates are positive integers less than 1000, and each radius is in the range 1 to 100.

Output

For each test case, print a single line containing the number of closed areas in that test case.

Examples5

Example 1

Input

Expected output

1
0

Example 2
Input
```
1
3
100 100 50
190 100 50
145 178 50
```
Expected output
```
1
```
Example 3
Input
```
1
3
100 100 50
170 100 50
135 161 50
```
Expected output
```
0
```
Example 4
Input
```
1
2
100 100 30
150 100 30
```
Expected output
```
0
```
Example 5
Input
```
1
3
100 100 20
300 300 20
700 200 30
```
Expected output
```
0
```