#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int inf = 1e8 ;
const int N = 3e6+9 ;
struct point
{
    int x , y , idx ;
};
point b[ 100 ] ;
int n , k , fa[ N ] , ans[N] ;
int Find( int x ){ return fa[x] == x ? x : fa[x] = Find( fa[x] ) ; }
long long dis( point a , point b )
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ;
}
void del()
{
    long long min_dis = (1ll<<63)-1 , idx_a = 0 , idx_b = 0 ;

    for( int i = 1 ; i <= k+1 ; i ++ )
    {
        long long md = (1ll<<63)-1 , idx = 0 ;
        for( int j = 1 ; j <= k+1 ; j ++ )
        {
            if( j == i ) continue ;
            if( dis(b[i],b[j]) < md )
            {
                md = dis(b[i],b[j]) ; idx = j ;
            }
        }
        if( md < min_dis )
        {
            min_dis = md ; idx_a = i ; idx_b = idx ;
        }
    }
    fa[Find(b[idx_a].idx)] = Find( b[idx_b].idx ) ;
    swap( b[idx_a] , b[k+1] ) ;

    //for( int i = 1 ; i <= n ; i ++ ) cout << Find(i) << " " ; cout << "\n" ;
}
void solve()
{
    cin >> n >> k ;
    queue<point>q ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        point a ;
        cin >> a.x >> a.y ; a.idx = i ;
        if( i <= k+1 ) b[i] = a ;
        else q.push( a ) ;
        fa[i] = i ;
    }

    if( n == k )
    {
        for( int i = 1 ; i <= n ; i ++ ) cout << i << " " ; cout << "\n" ;
        return ;
    }

    del() ;
    while( !q.empty() )
    {
        b[k+1] = q.front() ; q.pop() ;
        del() ;
    }

    int base = 1 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        if( Find(i) == i ) ans[i] = base++ ;
    }

    for( int i = 1 ; i <= n ; i ++ ) cout << ans[ Find(i) ] << " " ;
    cout << "\n" ;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tt = 1 ; cin >> tt ;
    while( tt-- ) solve() ;
    return 0 ;
}