#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
 
int T,n,m,f[(1<<20)],g[21][21];
 
double x[21],y[21];
 
double ABS(double a)
{
	return a<0?-a:a;
}
 
double operator -(pair<double,double>a,pair<double,double>b)
{
	return (fabs(a.first-b.first)+fabs(a.second-b.second));
}
 
pair<double,double> solve(int a,int b)
{
	double ra=x[a]*y[b]-x[b]*y[a];
	ra/=x[a]*x[b]*(x[b]-x[a]);
	double rb=y[a]/x[a]-ra*x[a];
	return make_pair(ra,rb);
}
 
int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		memset(f,0x3f,sizeof(f));
		memset(g,0,sizeof(g));
		f[0]=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
		int all=(1<<n)-1;
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				if(x[i]==x[j])
					continue;
				pair<double,double>tmp=solve(i,j);
				if(tmp.first>=-1e-7)
					continue;
				g[i][j]+=(1<<(i-1))+(1<<(j-1));
				for(int k=1;k<=n;k++)
					if(k!=i&&k!=j&&fabs(solve(i,k)-tmp)<1e-3)
						g[i][j]+=(1<<(k-1));
			}
		for(int i=1;i<=n;i++)
			g[i][i]=1<<(i-1),f[g[i][i]]=1;
		for(int S=0;S<=all;S++)
			for(int i=1;i<=n;i++)
				for(int j=i;j<=n;j++)
					f[S|g[i][j]]=min(f[S|g[i][j]],f[S]+1);
		cout<<f[all]<<endl;
	}
}