#include<iostream>
#include<cstdio>
#include<cmath>
#define N 1000
using namespace std;
const double inf=(double)(1e18);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
const long double delta[28]={0.69008650134455618019,0.81161262108749576694,0.87540838945196086662,0.91197960776400877059,0.93467232656760457221,0.94965689392795604729,0.96004620621442349204,0.96753530604602777654,0.97310729693425235265,0.97736282509057970103,0.98068512096831661484,0.98332779142424275864,0.98546397159533860588,0.98721507395988949973,0.98866825070979225121,0.98988735704332919685,0.99092003395449923531,0.99180240380728590388,0.99256225427490252233,0.99322124186513782718,0.99379644508457720686,0.99430147758075182463,0.99474729815379214770,0.99514280825949064102,0.99549529830789718066,0.99581078519119103909,0.99609427003152151148,0.99634993716803033070};
int T,n,d,length;
long double res,res2,sx[N+1],sy[N+1],tong[N+1],minn=inf;
int main()
{
	long double dst,dst2,rst,minn;
	int rt;
	T=read();
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),d=read(),res=res2=dst=dst2=length=rt=0,minn=inf;
		for (int i=1;i<=n;++i) cin>>sx[i]>>sy[i];
		for (int i=1;i<=n;++i) tong[++length]=sqrt((sx[i]-dst)*(sx[i]-dst)+(sy[i]-dst2)*(sy[i]-dst2));
		for (int i=max(3,d-5);i<=d;++i)
		{
			rst=0;
			for (int j=1;j<=length;++j) rst+=(tong[j]-delta[i-3])*(tong[j]-delta[i-3]);
			if (rst<minn) minn=rst,rt=i;
		}
		printf("%d\n",rt);
	}
	return 0;
}