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

#define endl '\n'

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


signed main() {
	ios::sync_with_stdio(false);
	cin.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({ abs(x[i] - x[j]) + abs(y[i] - y[j]),j });
			}
		}
		//
		vector<vector<int>>g(n + 1);
		for (int i = k + 1; i <= n; i++) {
			int mi = 2e9+1;
			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({ abs(x[v[w]] - x[i]) + abs(y[v[w]] - y[i]),v[w] });
					}
				}
				else {
					st[m].insert({ abs(x[v[m]] - x[i]) + abs(y[v[m]] - y[i]),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]);
			st[j.first].clear();
			for (int m = 1; m <= k + 1; m++) {
				if (m == j.first)continue;
				st[m].erase({ abs(x[v[m]] - x[v[j.first]]) + abs(y[v[m]] - y[v[j.first]]),v[j.first] });
			}
			
		}//return 0;
		vector<int>ans;
		auto dfs = [&](auto dfs, int u, int fa) ->void{
			ans.emplace_back(u);
			for (int i : g[u]) {
				if (i == fa)continue;
				dfs(dfs, i, u);
			}
			return;
		}; 
		vector<int>c(n + 1);
		int t = 0;
		for (int i = 1; i <= k + 1; i++) {
			if (st[i].size()) {
				t++;
				ans.clear();
				dfs(dfs, v[i], -1);
				
				for (auto x : ans) {
					c[x] = t;
				}
				
			}
		}
		for (int i = 1; i <= n; i++) {
			cout << c[i] << ' ';
		}
		cout << endl;
	}
}