#include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=,inf=1e9;

 int n,T,ans[N];

 struct P{ int x,y,id; }a[N];

 ll sqr(ll x){ return x*x; }

 ll dis(P a,P b){ return sqr(a.x-b.x)+sqr(a.y-b.y); }

 bool chk(int i,int k1,int k2){

     if (k1<i || k1>i+n) return ;

     if (k2<i || k2>i+n) return ;

     ll d1=dis(a[i],a[k1]),d2=dis(a[i],a[k2]);

     return d1==d2 ? a[k1].id<a[k2].id : d1>d2;

 }

 void solve(int l,int r,int L,int R){

     if (l>r) return;

     int mid=(l+r)>>,pos=;

     rep(i,L,R) if (chk(mid,i,pos)) pos=i;

     ans[mid]=pos>n ? pos-n : pos;

     solve(l,mid-,L,pos); solve(mid+,r,pos,R);

 }

 int main(){

     freopen("bzoj2739.in","r",stdin);

     freopen("bzoj2739.out","w",stdout);

     for (scanf("%d",&T); T--; ){

         scanf("%d",&n);

         rep(i,,n) scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i,a[n+i]=a[i];

         solve(,n,,n<<);

         rep(i,,n) printf("%d\n",ans[i]);

     }

     return ;

 }