#8 WA 读到6，正确5 代码：

#include<bits/stdc++.h>
#define ll long long
#define maxn 20
#define inf 1e16
using namespace std;
ll read(){
	ll f=1,k=0;
	char c=0;
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while((c>='0'&&c<='9')||c=='.'){
		if(c=='.'){c=getchar();continue;}
		k=k*10+c-'0';
		c=getchar();
	}
	return k*f;
}
void out(ll x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
ll gcd(ll a,ll b){
	if(a%b==0)return b;
	return gcd(b,a%b);
}
struct Hash{
    Hash *Next=NULL;
	ll am,az,bm,bz,zt=0;
}H[105];
void pushIn(Hash *&now,ll am,ll az,ll bm,ll bz,ll zt){
	if(now==NULL){
		now=new Hash;
		now->Next=NULL;
        now->am=am;
		now->az=az;
		now->bm=bm;
		now->bz=bz;
		now->zt=zt;
		return;
	}
    if(now->am==am&&now->az==az&&now->bm==bm&&now->bz==bz){
		(now->zt)|=zt;
			return;
	}
	pushIn(now->Next,am,az,bm,bz,zt);
}
ll ABS(ll x){
	return(x<0?(-x):x);
}
ll T,n,m,x[maxn],y[maxn],f[(1<<20)];
ll chkmin(ll a,ll b){
	return(a>b?b:a);
}
void Find(Hash *now,ll i){
    if(now==NULL)return;
	if((i&now->zt)==now->zt){
		f[i]=chkmin(f[i],f[i-now->zt]+1);
	}
	Find(now->Next,i);
}
void pre(){
    for(ll i=1;i<=100;i++)H[i].Next=NULL;
}
int main(){
//	freopen("g.in","r",stdin);
	T=read();
	while(T--){
		pre();
		n=read();m=read();
        for(ll i=1;i<=n;i++){
			x[i]=read();y[i]=read();
			for(ll j=1;j<i;j++){
				if(x[i]==x[j])continue;
                ll am=x[i]*x[j]*(x[i]-x[j]),az=x[j]*y[i]-x[i]*y[j],bm=am,bz=x[i]*x[i]*y[j]-x[j]*x[j]*y[i];
				if(am*az>=0)continue;
				ll ka=gcd(ABS(am),ABS(az)),kb=gcd(ABS(bm),ABS(bz));
				am=ABS(am)/ka;
				bm=ABS(bm)/kb;
				az=ABS(az)/ka;
				bz=ABS(bz)/kb;
				pushIn(H[am%97+1].Next,am,az,bm,bz,((1<<(i-1))|(1<<(j-1))));
			}
		}
        for(ll i=1;i<=(1<<n)-1;i++){
			f[i]=inf;
			for(ll j=1;j<=n;j++){
				if(i&(1<<(j-1))){
				f[i]=chkmin(f[i],f[i-(1<<(j-1))]+1);
				}
			}
			for(ll j=1;j<=97;j++){
				Find(H[j].Next,i);
			}
		}
        out(f[(1<<n)-1]);putchar('\n');
	}
	return 0;
}