#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1);
double fl[40];
int N,n,ans;double delt,delt_;
double x[1010],y[1010],x_,y_,dis;
void solve()
{
	x_=y_=dis=0;

	cin>>N>>n;
	for(int i=1;i<=N;i++)
	{
		cin>>x[i]>>y[i];
		x_+=x[i],y_+=y[i];
	}
	x_/=N,y_/=N;
	for(int i=1;i<=N;i++)
		dis+=(x_-x[i])*(x_-x[i])+(y_-y[i])*(y_-y[i]);
	dis/=N;
	delt=1e10;
	for(int i=3;i<=n;i++)
	{
		delt_=abs(fl[i]-dis)/fl[i];
		if(delt_<delt) delt=delt_,ans=i;
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);	
	
	for(int n=3;n<=30;n++) fl[n]=cos(PI/n)*cos(PI/n)*tan(PI/n)/(PI/n);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}