Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2589

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


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.


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


0 0 3
0 0 2

0 0 1
2 0 1

Sample Output


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