#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lf double

ll n,m;
lf xx[20],yy[20];
bool vis[20];
ll f[1<<20];
vector<ll> line;
queue<ll> num;

void add(ll x){
    line.push_back(x);
    num.push(x);
    f[x]=1;
}

void init(){
    memset(f,0x7f,sizeof(f));
    memset(vis,0,sizeof(vis));
    memset(xx,0,sizeof(xx));
    memset(yy,0,sizeof(yy));
    while(num.size()) num.pop();
    line.clear();

    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>xx[i]>>yy[i];
        add(1<<i);
    }

    for(ll r=1;r<n;r++)
    for(ll l=0;l<r;l++){
        lf x1=xx[l],x2=xx[r];
        lf y1=yy[l],y2=yy[r];
        lf a=(x1*y2-x2*y1)/(x1*x2*(x2-x1));
        lf b=(x2*x2*y1-x1*x1*y2)/(x1*x2*(x2-x1));
        if(a>0) continue;

        ll x=(1<<l)|(1<<r);
        for(ll k=r+1;k<n;k++)
        if(yy[k]==a*xx[k]*xx[k]+b*xx[k])
        x|=(1<<k);
        add(x);
    }
}
void solve(){
    while(!num.empty()){
        ll x=num.front();num.pop();
        if(x==(1<<n)-1){
            cout<<f[x]<<endl;
            break;
        }
        for(ll i=0;i<line.size();i++){
            ll y=x|line[i];
            if(f[y]<=f[x]+1) continue;
            f[y]=f[x]+1;
            num.push(y);
        }
    }
}

int main(){
    ll t;
    cin>>t;
    for(ll i=1;i<=t;i++){
        init();
        solve();
    }
    return 0;
}