#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#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;
	}
}

answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
answer.code:59:13: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
   59 | signed main() {
      |             ^
answer.code:59:13: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:59:13: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:59:13: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code: In function ‘int main()’:
answer.code:114:59: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
  114 |                 auto dfs = [&](auto dfs, int u, int fa) ->void{
      |                                                           ^~~~
answer.code:114:59: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:114:59: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:114:59: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:49:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~