#include<bits/stdc++.h>
using namespace std;
#define maxn 20 
const double zeros = 1e-8;
int T,n,m,line[maxn][maxn];
int min_x[1<<maxn];
int dp[1<<maxn];
void Equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){
	double D,D1,D2;
	D=(a1*b2-a2*b1);
	D1=(c1*b2-c2*b1);
	D2=(a1*c2-a2*c1);
	x=D1/D;
	y=D2/D;	
	return;
}
struct p{
	double x,y;
}point[maxn];
int main(){
	for(int i=0;i<(1<<18);i++){
		int j ;
		for(;j<=18&&i&(1<<(j-1));j++);
		min_x[i]=j;
	}
	cin>>T;
	while(T--){
		memset(line,0,sizeof(line));
		memset(dp,0x3f,sizeof(dp));
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>point[i].x>>point[i].y;
		}
		dp[0]=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){//处理抛物线 注意精度 
				if(fabs(point[i].x-point[j].x)<zeros)continue;
				double a,b;
				Equation(a,b,point[i].x*point[i].x,point[i].x,point[i].y,point[j].x*point[j].x,point[j].x,point[j].y);
				if(a>-zeros)continue;
				for(int k=1;k<=n;k++){
					if(fabs(a*point[i].x*point[i].x+b*point[i].x-point[i].y)<zeros){
						line[i][j]|=(1<<(k-1));
					}
				}
			}
		}
		for(int i=0;i<(1<<n);i++){
			int haveto=min_x[i];
			dp[i|(1<<(haveto-1))]=min(dp[i|(1<<(haveto-1))],dp[i]+1);
			for (int k=1;k<=n;k++){
				dp[i|line[haveto][k]]=min(dp[i|line[haveto][k]],dp[i]+1);
			}
		} 
		cout<<dp[(1<<n)-1]<<'\n';
	}
	return 0;
}