1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 #define N 200010
 5 const ll inf = 1e18;
 6 int n,i,id[N],root,cmp_d;
 7 int x, y;
 8 struct node{int d[2],l,r,Max[2],Min[2],val,sum,f;}t[N];
 9 bool cmp(const node&a,const node&b){return a.d[cmp_d]<b.d[cmp_d];}
10 void umax(int&a,int b){if(a<b)a=b;}
11 void umin(int&a,int b){if(a>b)a=b;}
12 void up(int x){
13     if(t[x].l){
14         umax(t[x].Max[0],t[t[x].l].Max[0]);
15         umin(t[x].Min[0],t[t[x].l].Min[0]);
16         umax(t[x].Max[1],t[t[x].l].Max[1]);
17         umin(t[x].Min[1],t[t[x].l].Min[1]);
18     }
19     if(t[x].r){
20         umax(t[x].Max[0],t[t[x].r].Max[0]);
21         umin(t[x].Min[0],t[t[x].r].Min[0]);
22         umax(t[x].Max[1],t[t[x].r].Max[1]);
23         umin(t[x].Min[1],t[t[x].r].Min[1]);
24     }
25 }
26 int build(int l,int r,int D,int f){
27     int mid=(l+r)>>1;
28     cmp_d=D,std::nth_element(t+l,t+mid,t+r+1,cmp);
29     id[t[mid].f]=mid;
30     t[mid].f=f;
31     t[mid].Max[0]=t[mid].Min[0]=t[mid].d[0];
32     t[mid].Max[1]=t[mid].Min[1]=t[mid].d[1];
33     //t[mid].val=t[mid].sum=0;
34     if(l!=mid)t[mid].l=build(l,mid-1,!D,mid);else t[mid].l=0;
35     if(r!=mid)t[mid].r=build(mid+1,r,!D,mid);else t[mid].r=0;
36     return up(mid),mid;
37 }
38 
39 ll dis(ll x1, ll y1, ll x, ll y) {
40     ll xx = x1-x, yy = y1-y;
41     return xx*xx+yy*yy;
42 }
43 ll dis(int p, ll x, ll y){//估价函数, 以p为子树的最小距离
44     ll xx = 0, yy = 0;
45     if(t[p].Max[0] < x) xx = x-t[p].Max[0];
46     if(t[p].Min[0] > x) xx = t[p].Min[0]-x;
47     if(t[p].Max[1] < y) yy = y-t[p].Max[1];
48     if(t[p].Min[1] > y) yy = t[p].Min[1]-y;
49     return xx*xx+yy*yy;
50 }
51 ll ans;
52 void query(int p){
53     ll dl = inf, dr = inf, d = dis(t[p].d[0], t[p].d[1], x, y);
54     if(d) ans = min(ans, d);
55 
56     if(t[p].l) dl = dis(t[p].l, x, y);
57     if(t[p].r) dr = dis(t[p].r, x, y);
58     if(dl < dr){
59         if(dl < ans) query(t[p].l);
60         if(dr < ans) query(t[p].r);
61     }
62     else {
63         if(dr < ans) query(t[p].r);
64         if(dl < ans) query(t[p].l);
65     }
66 }
67 
68 int main(){
69     int T; scanf("%d", &T);
70     while(T--){
71         scanf("%d", &n);
72         for(int i = 1; i <= n; i++){
73             scanf("%d%d", &t[i].d[0], &t[i].d[1]);
74             t[i].f = i;
75         }
76         int rt = build(1, n, 0, 0);
77         for(int i = 1; i <= n; i++){
78             ans = inf;
79             x = t[ id[i] ].d[0], y = t[ id[i] ].d[1];
80             query(rt);
81             printf("%lld\n", ans);
82         }
83     }
84     return 0;
85 }