#include<bits/stdc++.h>
#define ll long long
#define N 19
using namespace std;
int t,n,mm,dp[1<<N];
map<pair<double,double>,int> m;
struct node{
	double x,y;
}a[N];
bool cmp(node aa,node bb){
	if(aa.x==bb.x) return aa.y<bb.y;
	return aa.x<bb.x;
}
int main(){
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>mm;
		m.clear();
		for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
		sort(a,a+n,cmp);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j) continue;
				double x1=a[i].x,y1=a[i].y,x2=a[j].x,y2=a[j].y;
				if(fabs(x1-x2)<1e-8) continue;
				double k1=(y1*x2-y2*x1)/(x1*x1*x2-x2*x2*x1),k2=(y1-k1*x1*x1)/x1;
				if(k1>=0) continue;
				if(m.find({k1,k2})==m.end()){
					int mk=0;
					for(int k=0;k<n;k++){
						double fz=k1*a[k].x*a[k].x+k2*a[k].x;
						if(fabs(fz-a[k].y)<1e-6) mk|=(1<<k);
					}
					m[{k1,k2}]=mk;
				}
			}
		}
		for(int i=0;i<n;i++) m[{0.0+i,0.0}]=1<<i;
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for(int i=0;i<(1<<n);i++){
			if(dp[i]==0x3f) continue;
			for(auto it:m) dp[i|it.second]=min(dp[i|it.second],dp[i]+1);
		}
		cout<<dp[(1<<n)-1]<<endl;
	}
	return 0;
}