#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 abs(a.first - b.first) + abs(a.second - b.second);
}
pair<int, int> closest(const vector<pii>& 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) {
			pii cur = { i,j };
			int64_t curd = dis2(a[i], a[j]);
			if (curd < d) {
				ans = cur;
				d = curd;
			}
		}
	}
	return ans;
}
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];
		}
		set<int>s;
		for (int i = 1; i <= k; i++) {
			s.insert(i);
		}
		//
		
		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++) {
			
			vector<int> v;
			vector<pii> que;
			s.insert(i);
			for (auto si : s) {
				v.push_back(si);
				que.push_back({x[si],y[si]});
			}
			pii it=closest(que);
			int x = it.first, y = it.second;
			int ai = find(find, v[x]), bi = find(find, v[y]);
			p[ai] = bi;
			s.erase(v[x]);
			s.erase(v[y]);
			s.insert(v[x]);
			
			
			
		}//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;
	}
}