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

class DSU {
	vector<int> a;
public:
	DSU(int n) : a(n) {
		iota(a.begin(), a.end(), 0);
	}
	int query(int x) {
		if (a[x] != x)
			a[x] = query(a[x]);
		return a[x];
	}
	void merge(int x, int y) {
		a[query(x)] = query(y);
	}
};

using llf = long double;

struct P {
	int64_t x, y;
};

llf dis(P a, P b) {
	int64_t dx = a.x - b.x;
	int64_t dy = a.y - b.y;
	return sqrt(llf(dx * dx + dy * dy));
}
int64_t dis2(P a, P b) {
	int64_t dx = a.x - b.x;
	int64_t dy = a.y - b.y;
	return dx * dx + dy * dy;
}

pair<int, int> closest(const vector<P> &a) {
	int64_t d = dis2(a[0], a[1]);
	pair<int, int> ans = {0, 1};
	for (int i = 0; i < int(a.size()); ++i) {
		for (int j = i + 1; j < int(a.size()); ++j) {
			auto cur = pair{i, j};
			int64_t curd = dis2(a[i], a[j]);
			if (curd < d) {
				ans = cur;
				d = curd;
			}
		}
	}
	return ans;
	// struct cmp_y {
	// 	bool operator()(const pair<P, int> &p, const pair<P, int> &q) const {
	// 		return tie(p.first.y, p.second) < tie(q.first.y, q.second);
	// 	}
	// };
	// set<pair<P, int>, cmp_y> s;

	// pair<int, int> ans = {0, 1};
	// vector<int> o(a.size());
	// iota(o.begin(), o.end(), 0);
	// sort(o.begin(), o.end(), [&](int p, int q) {
	// 	return tie(a[p].x, a[p].y) < tie(a[q].x, a[q].y);
	// });
	// llf d = 1e100; int pt = 0;
	// for (int i = 0; i < int(a.size()); ++i) {
	// 	while (pt < i and a[o[i]].x - a[o[pt]].x >= d) {
	// 		s.erase({a[o[pt]], o[pt]});
	// 		pt += 1;
	// 	}
	// 	auto it = s.lower_bound({P(a[o[i]].x, a[o[i]].y - d), -1});
	// 	while (it != s.end() and it->first.y - a[o[i]].y < d) {
	// 		llf curd = dis(it->first, a[o[i]]);
	// 		if (curd < d) {
	// 			ans = {it->second, o[i]};
	// 			d = curd;
	// 		}
	// 		it++;
	// 	}
	// 	s.emplace(a[o[i]], o[i]);
	// }
	// return ans;
}


int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<P> a(n);
		for (auto &[x, y] : a)
			cin >> x >> y;
		DSU dsu(n);
		unordered_set<int> s;
		for (int i = 0; i < k; ++i)
			s.insert(i);
		for (int i = k; i < n; ++i) {
			vector<int> v;
			vector<P> que;
			s.insert(i);
			for (auto si : s) {
				v.push_back(si);
				que.push_back(a[si]);
			}
			auto [x, y] = closest(que);
			dsu.merge(v[x], v[y]);
			s.erase(v[x]);
			s.erase(v[y]);
			s.insert(v[x]);
		}
		vector<int> ans(n);
		for (int i = 0; i < n; ++i)
			if (dsu.query(i) == i)
				ans[i] = k--;
		for (int i = 0; i < n; ++i)
			cout << ans[dsu.query(i)] << " \n"[i + 1 == n];
	}
	return 0;
}