#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int T,n,m,ans;
bool flag;
const double eps=1e-8;
double tx,ty,a,b,x[20],y[20],pwa[100],pwb[100],gx[100],gy[100];
bool com(double p,double q)
{
	return fabs(p-q)<eps;
}
void dfs(int c,int w,int u)
{
	if(w+u>=ans)	return ;
	if(c>n)
	{
		ans=w+u;
		return ;
	}
	flag=0;
	for(int i=1;i<=w;i++)
	{
		if(com(pwa[i]*x[c]*x[c]+pwb[i]*x[c],y[c]))
		{
			dfs(c+1,w,u);
			flag=1;
			break;
		}
	}
	if(!flag)
	{
		for(int i=1;i<=u;i++)
		{
			if(com(gx[i],x[c]))	continue;
			a=(y[c]*gx[i]-gy[i]*x[c])/(x[c]*x[c]*gx[i]-gx[i]*gx[i]*x[c]);
			b=(gy[i]-a*gx[i]*gx[i])/gx[i];
			if(a>=0)	continue;
			tx=gx[i],ty=gy[i];
			for(int j=i;j<u;j++)	gx[j]=gx[j+1],gy[j]=gy[j+1];
			pwa[w+1]=a;
			pwb[w+1]=b;
			dfs(c+1,w+1,u-1);
			for(int j=u;j>i;j--)	gx[j]=gx[j-1],gy[j]=gy[j-1];
			gx[i]=tx,gy[i]=ty;
		}
		gx[u+1]=x[c],gy[u+1]=y[c];
		dfs(c+1,w,u+1);
	}
}
int main()
{
	cin>>T;
	while(T--)
	{
		/*memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(pwa,0,sizeof(pwa));
		memset(pwb,0,sizeof(pwb));
		memset(gx,0,sizeof(gx));
		memset(gy,0,sizeof(gy));*/
		cin>>n>>m;
		for(int i=1;i<=n;i++)	cin>>x[i]>>y[i];
		ans=100;
		dfs(1,0,0);
		cout<<ans<<endl;
	}
	return 0;
}