/*
* Problem :: 10216 / Count Circle Groups
*
* Kind :: Union Find
*
* Insight
* - 상호간에 통신이 가능한 진영끼리는 결집력 있는 한 그룹처럼 행동한다
* 적군 진영의 그룹 개수를 알아내야 한다
* + 그룹 내부의 진영끼리는 통신이 가능하다, 그룹 간에는 서로 통신이 불가능하다
* # Disjoint Set(서로소 집합)의 개수를 구해야 한다
* 진영끼리 연락되면 같은 그룹에 속하고
* 그렇지 않다면 서로 다른 그룹에 속한다
* -> Union Find 알고리즘을 적용하자
*
* Point
* - DFS 로도 BFS 로도 풀 수 있다
* + 다만, 다음 노드를 탐색할 때 연결되었는지 그렇지 않은지 매번 확인하기보다는
* 아예 배열을 따로 만들어서 처음에 각 진영끼리의 연결여부를 확인해주면
* 훨 효율적으로 탐색할 수 있다
* # 사실 처음 불때는 위와같은 아이디어로 BFS 로 풀었는데
* Union Find 가 훨씬 더 빠를 것 같아서 이번에는 그렇게 풀어보았다
* -> 그런데 BFS 가 더빠르네...?!?
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N;
struct Camp { int x, y, r; };
Camp C[3000];
int P[3000];
int R[3000];
// Set up : Functions Declaration
bool isConnected(int u, int v);
int find(int u);
void merge(int u, int v);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int T; cin >> T;
while (T--) {
cin >> N;
for (int i=0; i<N; i++) {
int x, y, r;
cin >> x >> y >> r;
C[i] = {x, y, r};
}
// Process
/* P[i] = i 번째 진영의 부모 노드, R[i] = i 번째 진영의 랭크 */
for (int i=0; i<N; i++) {
P[i] = i;
R[i] = 1;
}
int ans = N; /* 초기에는 각각의 진영를 하나의 그룹으로 간주 */
for (int i=0; i<N; i++) {
for (int j=i+1; j<N; j++) {
if (find(i) != find(j)) { /* i 번째 진영와 j 번째 진영의 부모 노드가
* 서로 다르다면 */
if (isConnected(i, j)) { /* i 번째 진영와 j 번째 진영이
* 통신이 가능하다면 */
merge(i, j); /* i 번째 진영와 j 번째 진영은 같은 그룹에 속함 */
ans--; /* 두 그룹이 하나의 그룹으로 통합되었으므로
* 전체 그룹의 개수 감소 */
}
}
}
}
// Control : Output
cout << ans << endl;
}
}
// Helper Functions
bool isConnected(int u, int v)
/* u 번째 진영와 v 번째 진영가 통신가능하다면 true 를 반환, 그 외 false 를 반환 */
{
Camp cu = C[u];
Camp cv = C[v];
int dy = cv.y - cu.y;
int dx = cv.x - cu.x;
int ru = cu.r;
int rv = cv.r;
/* 통신이 가능하려면 두 진영의 좌표간의 거리의 제곱이
* 두 진영의 반지름의 합의 제곱보다 같거나 작아야 함 */
return dy*dy + dx*dx <= (ru+rv)*(ru+rv);
}
int find(int u)
/* u 번째 진영의 부모 노드를 반환 */
{
if (P[u] == u) return u;
return P[u] = find(P[u]); /* 경로 최적화 */
}
void merge(int u, int v)
/* u 번째 진영와 v 번째 진영가 속한 그룹을 하나로 통합 */
{
int pu = find(u); /* u 번째 진영의 부모 노드 */
int pv = find(v); /* v 번째 진영의 부모 노드 */
/* pu 의 랭크가 항상 pv 의 랭크보다 같거나 크도록 함 */
if (R[pu] < R[pv]) {
swap(pu, pv);
}
/* pv 의 부모 노드를 pu 로 변경
* 이로써, u 번째 진영가 속한 그룹과 v 번째 진영가 속한 그룹이 하나로 통합됨 */
P[pv] = pu;
if (R[pu] == R[pv]) { /* pu 그룹과 pv 그룹의 랭크가 서로 같다면 */
R[pu]++; /* pu 그룹의 랭크 증가 */
}
}