Mandalas

Time limit1sMemory limit128 MB

Summary

Given up to 500 circles, count how many regions the arrangement of circles divides the plane into, handling tangency and duplicate circles exactly.

Level: Medium7 of 10
Topics: Geometry, Graph, Implementation, Math
Solved: No attempts yet

Problem

Shasita is drawing mandalas. First she draws several circles, and then she colours the regions that they divide the plane into.

Her younger sister Rice agrees to help: Rice will draw the circles and Shasita will colour them. Shasita does not want to colour a huge number of tiny regions, so she wants to fix in advance how many regions the circles will create. Rice, however, is not good at counting regions, so she asks you for help.

Given a mandala, that is, an arrangement of circles, determine how many regions it divides the plane into.

Input

The first line contains the number of test cases. Each test case has the following format:

one line with the integer $n$ ( $0 \le n \le 500$ ), the number of circles;
$n$ lines follow, each with three integers $x_i$ , $y_i$ , $r_i$ describing the $i$ -th circle, whose centre is $(x_i, y_i)$ and whose radius is $r_i$ , with $|x_i|, |y_i| \le 1000$ and $0 < r_i \le 1000$ .

Output

For each test case, output a single integer on its own line: the number of regions into which the circles divide the plane $\mathbb{R}^2$ .

Examples4

Example 1

Input

Expected output

2
3
6

Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
1
2
0 0 3
0 0 5
```
Expected output
```
3
```
Example 4
Input
```
1
2
0 0 5
6 0 5
```
Expected output
```
4
```