#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<char,int> PCI;
typedef pair<string,int> PSI;
typedef pair<int, char> PIC;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define lson rt<<1
#define rson rt<<1|1
typedef array<int,2> pr;
#define ull unsigned long long
const unsigned int mask =  (chrono::steady_clock::now().time_since_epoch().count());
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//gcd(a,b)=gcd(a,b-a)(b>a);
//__builtin_count()
inline int lcm(int a, int b){return a / gcd(a, b) * b;}//lcm(n,m)=n*m/gcd(n,m)
const ll mod = 998244353;
const int inv2 = (mod+1)/2;
int addmod(int &x, int y) {x = (x + y >= mod ? x + y - mod : x + y);return 1;}
ll qpow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll inv(int x){return qpow(x,mod-2);}
inline void read(__int128 &x)
{
    char c; while(!((c=getchar())>='0'&&c<='9'));
    x=c-'0';
    while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
int o[200010],on;
inline void output(__int128 x)
{
    on=0;
    while(x) o[++on]=x%10,x/=10;
    for(int i=on;i>=1;i--) cout<<o[i];
}
#define maxn 2000010
struct point{
    ll x,y;
}a[maxn];
#define cp const point&
ll sqr(ll x)
{
    return x*x;
}
ll dis(cp a,cp b)
{
    return sqr(a.x-b.x)+sqr(a.y-b.y);
}
int n,K;
pair<ll,int> id[maxn];
void solve()
{
    cin>>n>>K;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    int x=0;
    for(int i=1;i<=n;i++)
    {
        id[i]={dis(a[i],a[x]),x};
    }
    unordered_map<int,int> rev(K+10);
    rev[0]=0;
    for(int k=1;k<K;k++)
    {
        x=0;
        for(int i=2;i<=n;i++)
        {
            if(id[x]<id[i])
            {
                x=i;
            }
        }
        rev[x]=k;
        for(int i=1;i<=n;i++)
        {
            id[i]=min(id[i],mp(dis(a[x],a[i]),x));
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<rev[id[i].second]+1<<" ";
    }
    cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
int t;
cin>>t;
while(t--)
    solve();
return 0;
}