#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define int long long
using pii = pair<int, int>;
using ll = long long;

int dis2(pii a, pii b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	cin >> tt;
	while (tt--) {
		int n, k;
		cin >> n >> k;
		vector<int>x(n + 1), y(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> x[i] >> y[i];
		}
		vector < set<pii> >st(k + 2);
		vector<int>v(k + 2);
		for (int i = 1; i <= k; i++) {
			v[i] = i;
		}
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= k; j++) {
				if (i == j)continue;
				st[i].insert({ dis2({x[i],y[i]},{x[j],y[j]}),j});
			}
		}
		//
		//vector<vector<int>>g(n + 1);
		vector<int>p(n + 1);
		for (int i = 1; i <= n; i++) {
			p[i] = i;
		}
		auto find = [&](auto find, int x)->int {
			if (p[x] != x)return p[x] = find(find, p[x]);
			return p[x];
		};
		for (int i = k + 1; i <= n; i++) {
			int mi = 9e18 ;
			pii j = { 0,0 };
			for (int m = 1; m <= k + 1; m++) {
				if (st[m].size() == 0) {
					v[m] = i;
					for (int w = 1; w <= k + 1; w++) {
						if (w == m)continue; 
						st[m].insert({ dis2({x[i],y[i]},{x[v[w]],y[v[w]]}),v[w] });
					}
				}
				else {
					st[m].insert({ dis2({x[i],y[i]},{x[v[m]],y[v[m]]}),i });
					pii tmp = (*st[m].begin());
					if (mi > tmp.first) {
						mi = tmp.first;
						j = { m,tmp.second };
					}
				}
			}
			//g[v[j.first]].emplace_back(j.second);
			//g[j.second].emplace_back(v[j.first]);
			int ai = find(find, v[j.first]), bi = find(find, j.second);
			p[ai] = bi;
			st[j.first].clear();
			for (int m = 1; m <= k + 1; m++) {
				if (m == j.first)continue;
				st[m].erase({ dis2({x[v[j.first]],y[v[j.first]]},{x[v[m]],y[v[m]]}),v[j.first] });
			}

		}return 0;


		vector<int>c(n + 1);
		for (int i = 1; i <= n; i++) {
			if (find(find, i) == i) {
				c[i] = k--;
			}
		}
		for (int i = 1; i <= n; i++) {
			cout << c[find(find, i)] << ' ';
		}
		cout << endl;
	}
}