#include<bits/stdc++.h>
using namespace std;
const int N=18;const double eps=1e-6;
int T,n,typ,line[N][N];
double x[N],y[N];
int dp[1<<N];
int main(){
    cin>>T;
    while(T--){
        cin>>n>>typ;
        for(int i=0;i<n;i++){
            cin>>x[i]>>y[i];
        }
        memset(dp,127,sizeof(dp)),memset(line,0,sizeof(line));
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(abs(x[i]-x[j])>eps){
                    double a=(y[i]/x[i]-y[j]/x[j])/(x[i]-x[j]),b=y[i]/x[i]-a*x[i];
                    if(a<0){
                        for(int k=0;k<n;k++){
                            if(abs(a*x[k]*x[k]+b*x[k]-y[k])<eps){
                                line[i][j]+=(1<<k);
                            }
                        }
                    }
                }
            }
        }
        dp[0]=0;
        for(int S=0;S<(1<<n);S++){
            for(int i=0;i<n;i++){
                if((S>>i)&1){
                    dp[S]=min(dp[S],dp[S-(1<<i)]+1);
                }
                for(int j=i+1;j<n;j++){
                    if((S&line[i][j])==line[i][j]){
                        dp[S]=min(dp[S],dp[S-line[i][j]]+1);    
                    }
                }
            }
        }
        cout<<dp[(1<<n)-1]<<'\n';
    }
}