#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1);
mt19937 zsh(20070610);
struct Point{
	double x,y;
	Point operator+(const Point A)const{return Point{x+A.x,y+A.y};}
	void operator+=(const Point A){x+=A.x,y+=A.y;}
};
inline double pow(double A){return A*A;}
double dis(Point A,Point B){return sqrt(pow(A.x-B.x)+pow(A.y-B.y));}
Point py(Point O,double a){return Point{O.x+cos(a),O.y+sin(a)};}
struct Line{
	double A,B;
	void calc(Point p1,Point p2)
	{
		A=(p1.y-p2.y)/(p1.x*p2.y-p2.x*p1.y);
		B=(p1.x-p2.x)/(p1.y*p2.x-p2.y*p1.x);
	}
}l[40];
double dis(Line L,Point A){return fabs(L.A*A.x+L.B*A.y+1)/sqrt(L.A*L.A+L.B*L.B);}

int N,n,ans;double bst;
Point O,T,p[1010],p2[1010];
double jd[1010];
double calc(Point O)
{
	double ret=0;
	for(int i=1;i<=N;i++)
		ret+=pow(dis(O,p[i])-1);
	return ret;
}
double cur,nw,mn;
bool cmp(Point A,Point B){return dis(A,O)>dis(B,O);}
pair<int,double> p_[1010];
vector<double> ag;
double Tk[40];
void solve()
{
	vector<double>().swap(ag);
	O.x=O.y=0;

	cin>>N>>n;
	for(int i=1;i<=N;i++)
	{
		cin>>p[i].x>>p[i].y;
		O+=p[i];
	}
	O.x/=N,O.y/=N;

	cur=calc(O);
	for(double T=0.1;T>0.0001;T*=0.98)
	{
		for(int dx=-1;dx<=1;dx++) for(int dy=-1;dy<=1;dy++)
			if((nw=calc(Point{O.x+dx*T,O.y+dy*T}))<cur)
				cur=nw,O.x+=dx*T,O.y+=dy*T;
	}

	sort(p+1,p+N+1,cmp);
	for(int i=1;i<=20;i++)
	{
		nw=atan2(p[i].y-O.y,p[i].x-O.x);
		for(int d=-1;d<=1;d++)
			ag.push_back(nw+(1.*d/N)*2*PI);
	}

	for(int i=1;i<=N;i++)
		jd[i]=atan2(p[i].y-O.y,p[i].x-O.x);

	bst=1e10;
	for(int d=max(3,n-5);d<=n;d++)
	{
		cur=2*PI/d;
		for(double a:ag)
		{
			for(int i=0;i<d;i++)
			{
				Tk[i]=a+cur*i;
				if(Tk[i]>PI) Tk[i]-=2*PI;
			}
			sort(Tk,Tk+d);Tk[d]=Tk[0];
			for(int i=0;i<d;i++)
				l[i].calc(py(O,Tk[i]),py(O,Tk[i+1]));

			nw=0;
			for(int i=1;i<=N;i++)
			{
				for(int j=0;j<d;j++) if((Tk[j]<=jd[i]&&jd[i]<=Tk[j+1])||j==d)
				{
					nw+=pow(dis(l[j],p[i]));
					break;
				}
			}
			if(nw<bst) bst=nw,ans=d;
		}

	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}