Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2589
Circles

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Consider N different circles on the plane. They divide it to several parts, you have to find the number of these parts.

For the purpose of this problem the circle of radius r with center (x0, y0) is the set of points


Input

The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 20) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each test case contains N - the number of circles (1 <= N <= 50). Next N lines contain three integer numbers x0, y0, and r each - the coordinates of the center and the radius of the circle. All coordinates do not exceed 103 by their absolute value, all radii are positive and do not exceed 103. No two circles coincide.


Output

For each test case, output K - the number of parts circles divide the plane to, in a single line.

Due to floating point precision losses possible, do not consider parts with area not exceeding 10-10.


Sample Input

2

2
0 0 3
0 0 2

2
0 0 1
2 0 1

Sample Output

3
3


Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #5
Submit    Status