#include <bits/stdc++.h>

typedef long long ll;
typedef std::pair<int, int> point;
const ll inf = 1e18;
const int N = 2e6 + 5;
#define x first
#define y second

int n, k, init[32], res[N];
ll dis[N];
point a[N];

inline ll dist(point a, point b) {
	return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
	memset(dis, 0x3f, sizeof(ll) * n);
    for (int i = 0; i < k; ++i) {
    	for (int j = 1; j < n; ++j) if (dis[j] > dis[init[i]]) init[i] = j;
        for (int j = 0; j < n; ++j) dis[j] = std::min(dis[j], dist(a[j], a[init[i]]));
    }
    for (int i = 0; i < n; ++i) {
        ll mn = inf;
        for (int j = 0; j < k; ++j) {
            ll tmp = dist(a[i], a[init[j]]);
            if (tmp < mn) res[i] = j + 1, mn = tmp;
        }
    }
    for (int i = 0; i < n; ++i) printf("%d ", res[i]); puts("");
}

int main() {
	int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}