#include<bits/stdc++.h>
using namespace std;
int t,n,m,f[1<<19],h[400],top,ans;
double x[20],y[20],e=1e-8;
int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(n==0){
			cout<<0<<endl;
			continue;
		}
		top=0,ans=INT_MAX;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
			h[++top]=(1<<(i-1));
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				double am=(x[i]-x[j])*x[i]*x[j];
				if(abs(am)<e)
				continue;
				double a=(y[i]*x[j]-y[j]*x[i])/am;
				double b=(y[i]*(x[j]*x[j])-y[j]*(x[i]*x[i]))/(x[i]*x[j]*(x[j]-x[i]));
				if(a>=-e)
				continue;
				h[++top]=(1<<(i-1));
				h[top]|=(1<<(j-1));
				for(int k=1;k<=n;k++){
					if(k==i||k==j)
					continue;
					if(abs(a*(x[k]*x[k])+b*x[k]-y[k])<e){
						h[top]|=(1<<(k-1));
					}
				}
			}
		}
		sort(h + 1, h + top + 1);
		top = unique(h + 1, h + top + 1) - (h + 1);
		memset(f,0x3f,sizeof(f));
        f[0]=0;
		for(int i=0;i<(1<<n);i++){
			for(int k=1;k<=top;k++){
				if(f[i]>1e8)
				continue;
				f[i|h[k]]=min(f[i|h[k]],f[i]+1);
			}
		}
			ans=min(ans,f[(1<<n)-1]);
		cout<<ans<<endl;
	}
	return 0;
}