#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], leader[25];
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);
        int tp = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= tp; ++j)
                if (abs2(arr[i] - leader[j]) <= mid) {
                    num[i] = j;
                    break;
                }
            if (!num[i]) leader[++tp] = arr[i], num[i] = tp;
            if (tp >= k + 1) return false;
        }
        return true;
    };

    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();
    }
}