#include<bits/stdc++.h>
using namespace std;
struct point {
	long long x,y;
};
long long dist(point a,point b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main(){
	int z;
	cin>>z;
	for(int l=1;l<=z;l++){
		long long n,k;
		cin>>n>>k;
		vector<point> p(n+1);
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y;
		}
		vector<int> h,flag(n+1);
		h.push_back(1);
		flag[1]=1;
		for(int i=2;i<=k;i++){
			long long sum=4e18,q,s;
			if(i>2){
				for(int j=2;j<=n;j++){
					if(flag[j]) continue;
					for(auto it:h){
						if(dist(p[it],p[j])<sum){
							sum=dist(p[it],p[j]);
							q=j;
						}
					}
				}
			}
			
			sum=-4e18;
			for(int j=2;j<=n;j++){
				if(flag[j]) continue;
				if(dist(p[q],p[j])>sum){
					sum=dist(p[q],p[j]);
					s=j;
				}
			}
			flag[s]=1;
			h.push_back(s);
		}
		for(int i=1;i<=n;i++){
			long long sum=4e18,q;
			for(int j=0;j<k;j++){
				if(dist(p[i],p[h[j]])<sum){
					sum=dist(p[i],p[h[j]]);
					q=j+1;
					
				}
			}
			cout<<q<<' ';
		}
		cout<<endl;
	}
	return 0;
}