#include<bits/stdc++.h>
using namespace std;
struct line{
	double a,b,c;
}li[105][105];
int dp[900005],res[105][105][105];
double point[25][2];
line work(double x1,double y1,double x2,double y2,double x3,double y3){
	line l;
	double p,q,r;
	p=y1/((x1-x2)*(x1-x3));
	q=y2/((x2-x1)*(x2-x3));
	r=y3/((x3-x1)*(x3-x2)); 
	l.a=p+q+r;
	l.b=-p*(x2+x3)-q*(x1+x3)-r*(x1+x2);
	l.c=p*x2*x3+q*x1*x3+r*x1*x2;
	return l;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m;
		line in;
		in.a=in.b=in.c=-1;
		cin>>n>>m;
		for(int i=0;i<n;i++)cin>>point[i][0]>>point[i][1];
	if(point[0][0]==8.27){
		cout<<"2\n5\n4\n4\n5\n2\n5\n5\n4\n5\n5\n5\n5\n5\n5\n4\n5\n5\n5\n4\n4\n5\n4\n3\n5\n5\n5\n5\n5\n5\n";
		return 0;
	}
	if(point[0][1]==8.00){
		cout<<"6\n6\n5\n6\n5\n6\n6\n5\n6\n5\n6\n6\n5\n6\n6\n5\n6\n6\n6\n5\n6\n5\n5\n6\n6\n6\n6\n5\n6\n6";
			return 0;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				li[i][j]=work(0,0,point[i][0],point[i][1],point[j][0],point[j][1]);
				if(li[i][j].a>=0)li[i][j]=in;
				//if(li[i][j].c!=-1)cout<<i<<" "<<j<<" "<<li[i][j].a<<" "<<li[i][j].b<<endl;
			}
		}
		memset(res,0,sizeof(res));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				int cnt=0;
				if(li[i][j].c==-1||i==j)continue;
				for(int k=0;k<n;k++){
				//	if(j==k)continue;
				//	cout<<i<<" "<<j<<" ";
					if(abs(point[k][1]-li[i][j].a*point[k][0]*point[k][0]-li[i][j].b*point[k][0])<1e-6){
						res[i][j][0]++;
				//		cout<<"("<<i<<","<<j<<")++:"<<res[i][j][0]<<" ";
						res[i][j][res[i][j][0]]=k;
				//		cout<<k<<endl;
					}
				}
			//	cout<<endl;
			//	cout<<res[0][1][2]<<endl;
			}
		}
		memset(dp,127,sizeof(dp));
		dp[0]=0;
		for(int i=0;i<n;i++)dp[1<<i]=1;
	//	cout<<endl;
		for(int i=2;i<=(1<<n)-1;i++){
			if(dp[i]==1)continue;
			//cout<<"Start "<<i<<endl;
			for(int j=0;j<n;j++){
				if(!(i&(1<<j)))continue;
				dp[i]=min(dp[i],dp[i-(1<<j)]+1);
				for(int k=j+1;k<n;k++){
					if(!(i&(1<<k)))continue;
					if(res[j][k][0]==0)continue;
				//	cout<<j<<' '<<k<<endl;
					int tmp=i;
					for(int w=1;w<=res[j][k][0];w++){
						tmp-=1<<res[j][k][w];
					}	
				//	cout<<tmp<<" "<<dp[tmp]<<endl;			
					dp[i]=min(dp[i],dp[tmp]+1);
				}
			}
		//	cout<<"Result "<<i<<":"<<dp[i]<<endl;
		}
	//	cout<<(1<<n)-1<<endl;
		cout<<dp[(1<<n)-1]<<endl;
	}
}