#include <bits/stdc++.h>
using namespace std;
double x[20],y[20];
int t,n,m;
int find(int x)
{
	int cnt=-1;
	while(x>0)
	{
		cnt++;
		if(x%2==0)return cnt;
		x/=2;
	}
	return cnt+1;
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		int dp[(1<<20)]={},f[20][20]={};
		int full=(1<<n)-1;
		for(int i=0;i<n;i++)
		{
			cin>>x[i]>>y[i];
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i==j)
				{
					f[i][j]=(1<<i);
					continue;
				}
				double b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*(x[j]-x[i]));
				double a=-(y[i]*x[j]-y[j]*x[i])/(x[j]*x[i]*(x[j]-x[i]));
				if(a>=0)continue;
				f[i][j]=(1<<i)|(1<<j);
				for(int k=0;k<n;k++)
				{
					if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<1e-8)f[i][j]|=(1<<k);
				}
			}
		}
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for(int i=0;i<(1<<n);i++)
		{
			int x=find(i);
			for(int j=0;j<n;j++)
			{
				int t=i|f[x][j];
				t&=full;
				dp[t]=min(dp[t],dp[i]+1);
			}
		}
		cout<<dp[(1<<n)-1]<<endl;
	}
	return 0;
}