#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

pll operator-(const pll &a, const pll &b) { return pll(a.X - b.X, a.Y - b.Y); }
ll dot(const pll &a, const pll &b) { return a.X * b.X + a.Y * b.Y; }
ll abs2(const pll &a) { return dot(a, a); }

const ll MAXC = 2e18;
pll arr[2000005];
int num[2000005];

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i].X >> arr[i].Y;

    auto check = [&](ll mid) {
        fill_n(num + 1, n, 0);
        for (int t = 1; t <= k + 1; ++t) {
            int cur = 0;
            for (int i = 1; i <= n; ++i)
                if (!num[i]) {
                    if (!cur) cur = i, num[i] = t;
                    else if (abs2(arr[cur] - arr[i]) <= mid)
                        num[i] = t;
                }
            if (!cur) return true;
        }
        return false;
    };

    ll l = -1, r = MAXC;
    while (r - l > 1) {
        ll mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid;
    }
    check(r);
    for (int i = 1; i <= n; ++i)
        cout << num[i] << " \n"[i == n];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}