#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,m,line[400],f[1<<20],A,cnt,i,j,k;
double x[20],y[20],a,b,eps=1e-6;
double abs(double z){return z<0?-z:z;}
int Main()
{
	freopen("angrybirds.in","r",stdin);freopen("angrybirds.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(f,20,sizeof(f));
		memset(line,0,sizeof(line));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		f[0]=0;A=(1<<n)-1;cnt=0;
		for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
		for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)
		{
			if(abs(x[i]-x[j])<eps)continue;
			if((y[i]/x[i]-y[j]/x[j])/(x[i]-x[j])>=-eps)continue;
			line[++cnt]|=1<<(i-1);
			line[cnt]|=1<<(j-1);
			a=(y[i]*x[j]-x[i]*y[j])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
			b=(y[i]-a*x[i]*x[i])/x[i];
			for(k=1;k<=n;k++)
				if(abs(a*x[k]+b-y[k]/x[k])<eps)
					line[cnt]|=1<<(k-1);
		}
		for(i=1;i<=n;i++)line[++cnt]|=(1<<(i-1));
		for(i=0;i<=A;i++)for(j=1;j<=cnt;j++)
			f[i|line[j]]=min(f[i|line[j]],f[i]+1);
		printf("%d\n",f[A]);
	}
	return 0;
}
int main(){;}
int syy=Main();