In the following figure, if mine 4 initiates, mines 3 and 6 will explode. If mine 1 initiates, mine 4 will explode. The following explosion will result mines 3 and 6 to explode. Therefore, initiating mines 1, 2, and 5 will cause all the mines to explode.

Given N mines with their explosion performance as square areas in a two-dimensional plane, write a program that determines the minimum number of mines that needs to be initiated to explode all given mines.

Input 

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer N ( 3N2, 000), which represents the number of mines. In the following N lines, each line contains three integers x, y and d, where x and y are the coordinates of the mine in the plane and d is the size of one side of the square which representing the explosion performance ( 1x, y10, 000, 000, 1d1, 000, 000).

Output 

Your program is to write to standard output. Print exactly one line for each test case. Print the minimum number of mines that needs to be initiated to explode all given mines.

The following shows sample input and output for two test cases.

Sample Input 

2
6
6 11 10
10 17 4
12 10 4
10 7 6
5 4 6
12 5 2
4
6 7 8
9 10 4
11 5 4
15 9 8

Sample Output 

3
2

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
struct E {
    int x, y, d;
    bool operator<(const E &a) const {
        return x < a.x;
    }
} D[10000];
#define maxN 4096
vector<int> g[maxN];
int vfind[maxN], findIdx;
int stk[maxN], stkIdx;
int in_stk[maxN], visited[maxN];
int scc_cnt;
int contract[maxN];
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd]; // back edge
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(!visited[*it])
            mn = min(mn, scc(*it));
        if(in_stk[*it])
            mn = min(mn, vfind[*it]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int t, n, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].d);
        sort(D, D+n);
        int indeg[2005] = {}, x, y, d;
        for(i = 0; i < n; i++) {
            g[i].clear();
            d = D[i].d;
            x = D[i].x;
            y = D[i].y;
            for(j = i+1; j < n; j++) {
                if(D[j].x - x > d/2.0)
                    break;
                if(y-d/2.0 <= D[j].y && D[j].y <= y+d/2.0)
                    g[i].push_back(j);
            }
            for(j = i-1; j >= 0; j--) {
                if(x - D[j].x > d/2.0)
                    break;
                if(y-d/2.0 <= D[j].y && D[j].y <= y+d/2.0)
                    g[i].push_back(j);
            }
        }
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        scc_cnt = 0;
        for(i = 0; i < n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        for(i = 0; i < n; i++) {//become DAG
            x = contract[i];
            //printf("contract %d\n", x);
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y)
                    indeg[y]++;
            }
        }
        int ret = 0;
        for(i = 0; i < n; i++)
            if(indeg[i] == 0 && i == contract[i])
                ret++;
        printf("%d\n", ret);
    }
    return 0;
}