1 // hdu 3832
2 #include <iostream>
3 #include <cstring>
4 #include <queue>
5 #include <algorithm>
6 using namespace std;
7
8 /////二维数组建边
9 #define maxn 205
10 #define MP make_pair
11 const int inf=0x3f3f3f3f;
12
13 int N; //N顶点数
14 int dist[maxn][maxn],mp[maxn][maxn];
15 void dijstra(int s)
16 {
17 typedef pair<int,int> pii;
18 priority_queue<pii, vector<pii>, greater<pii > > que;
19 dist[s][s]=0;
20 que.push(MP(0,s));
21 int d, v;
22 pair<int,int> tmp;
23 while(!que.empty())
24 {
25 tmp=que.top();
26 que.pop();
27 d = tmp.first, v = tmp.second;
28 if(d > dist[s][v])
29 continue;
30 for(int i=0; i<N; ++i)
31 if(dist[s][i]>dist[s][v]+mp[v][i])
32 {
33 dist[s][i]=dist[s][v]+mp[v][i];
34 que.push(MP(dist[s][i],i));
35 }
36 }
37 }
38
39 void init()
40 {
41 memset(mp, 0x1f, sizeof(mp));
42 memset(dist, 0x1f, sizeof(dist));
43 }
44
45 ////////
46
47 /////vector建边
48 #ifdef _no
49
50 const int inf=(1LL<<30);
51 #define MP make_pair
52
53 vector<pii> mp[MAXN];
54 inline void add_edge(int u,int v, lld cost){
55 mp[u].push_back(MP(v, cost));
56 mp[v].push_back(MP(u, cost));
57 }
58
59 int N; //N顶点数
60 vector<lld> dist;
61 void dijstra(int s)
62 {
63 dist.assign(N+1, inf);
64 typedef pair<int,int> pii;
65 priority_queue<pii, vector<pii>, greater<pii> > que;
66 dist[s]=0;
67 que.push(MP(0,s));
68 while(!que.empty())
69 {
70 pii tmp=que.top();
71 que.pop();
72 int vv = tmp.second;
73 int d = tmp.first;
74 if(d > dist[vv])
75 continue;
76 for(int i=0; i<mp[vv].size(); ++i)
77 {
78 int v2 = mp[vv][i].first;
79 lld tx = mp[vv][i].second;
80 if(dist[v2]>dist[vv]+tx)
81 {
82 dist[v2]=dist[vv]+tx;
83 que.push(MP(dist[v2],v2));
84 }
85 }
86 }
87 }
88
89 void init()
90 {
91 for(int i=0; i<=N; ++i)
92 mp[i].clear();
93 }
94 /////*/
95 #endif
96
97 struct circle{
98 int x, y, rad;
99 } code[205];
100
101 bool judge(circle a, circle b)
102 {
103 int tmp = (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
104 if(tmp <= (a.rad+b.rad)*(a.rad+b.rad))
105 return true;
106 else
107 return false;
108 }
109
110 int main()
111 {
112 int T;
113 scanf("%d", &T);
114 while(T--)
115 {
116 scanf("%d", &N);
117 init();
118 for(int i=0; i<N; ++i)
119 scanf("%d %d %d", &code[i].x, &code[i].y, &code[i].rad);
120 for(int i=0; i<N; ++i)
121 for(int j=0; j<N; ++j)
122 if(judge(code[i], code[j]))
123 mp[i][j] = 1;
124 dijstra(0);
125 dijstra(1);
126 dijstra(2);
127 int res = inf;
128 for(int i=0; i<N; ++i)
129 {
130 res = min(res, dist[0][i]+dist[1][i]+dist[2][i]);
131 }
132 if(res > 10000 || res<2)
133 printf("-1\n");
134 else
135 printf("%d\n", N-res-1);
136 }
137 }