#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<18;
const double esp=1e-8;
typedef pair<double,double>PDD;
#define x first
#define y second
int n,m;
PDD q[N];
int path[N][N];//存i,j两点连的抛物线能覆盖的点的状态
int f[M]; //覆盖的点的状态是i的情况下需要的抛物线数量
int cmp(double x,double y) {
    if(abs(x-y)<esp) return 0;
    if(x>y) return 1;
    return -1;
}
int main() {
    int T;
    cin>>T;
    while(T--) {
        memset(f,0x3f,sizeof f);
        memset(path,0,sizeof path);
        cin>>n>>m;
        for(int i=0; i<n; i++)cin>>q[i].x>>q[i].y;
        for(int i=0; i<n; i++) {
            path[i][i]=1<<i; //只有一个点，那么这条抛物线就只能覆盖当前点
            for(int j=0; j<n; j++) {
                double x1=q[i].x,y1=q[i].y;
                double x2=q[j].x,y2=q[j].y;
                if(x1==x2)continue; //两点平行y轴不可能被同一条抛物线覆盖
                double a,b;
                a=(y1/x1-y2/x2)/(x1-x2);
                b=y1/x1-a*x1;
                if(cmp(a,0)>=0) continue; //抛物线开口向下,必须有a<0
                int state=0;
                for(int k=0; k<n; k++) {
                    //枚举所有点，统计a,b这条抛物线能覆盖多少点
                    double x=q[k].x,y=q[k].y;
                    if(cmp(a*x*x+b*x,y)==0)state+=1<<k; //能覆盖点k
                }
                path[i][j]=state; //经过点i,j的抛物线能覆盖的点
            }
        }
        f[0]=0;
        for(int i=0; i+1<1<<n; i++) { //枚举0~ (1<<n)-1的覆盖状态
            int x=0;
            for(int j=0; j<n; j++) //任意找到i状态下没有覆盖的点
                if(!(i>>j &1)) {
                    x=j;
                    break;
                }
            for(int j=0; j<n; j++) //枚举所有经过该点的抛物线来更新状态
                f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);
        }

        cout<<f[(1<<n)-1]<<endl;//输出全覆盖的状态
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=1<<18+1,M=11,K=60000;
const double esp=1e-8;
ll i,j,n,k,m,T,ans;
ll f[N];
ll pa[19][19],st;
double x,y;
struct xx
{
    double x,y;
}q[19];
ll cmp(double x,double y)
{
    if(abs(x-y)<esp)return 0;
    if(x>y)return 1;
    else return -1;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        memset(f,0x3f,sizeof f);
        memset(pa,0,sizeof pa);
        for(i=0;i<n;i++)
        {
            cin>>q[i].x>>q[i].y;
            pa[i][i]=1<<i;
        }
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                if(i==j)continue;
                double xa=q[i].x,ya=q[i].y;
                double xb=q[j].x,yb=q[j].y;
                if(xa==xb)continue;
                double a=((ya/xa)-(yb/xb))/(xa-xb),b=ya/xa-a*xa;
                //cout<<a<<" "<<b<<endl;
                if(cmp(a,0)>=0)continue;
                st=0;
                for(k=0;k<n;k++)
                {
                    if(cmp(q[k].x*q[k].x*a+b*q[k].x,q[k].y)==0)
                        pa[i][j]=pa[i][j]|(1<<k);
                }
            //  pa[i][j]=st;
            }
        f[0]=0;
//      for(i=0;i<n;i++)
//      {
//          for(j=0;j<n;j++)cout<<pa[i][j]<<" ";
//          cout<<endl;
//      }
        for(i=0;i+1<(1<<n);i++)
        {
            ll x=0;
            for(j=0;j<n;j++)
            {
                if((i>>j  &1)==0)
                {
                    x=j;break;
                }
            }
            for(j=0;j<n;j++)
                f[i|pa[x][j]]=min(f[i|pa[x][j]],f[i]+1);
        }
        cout<<f[(1<<n)-1]<<endl;
    }
    return 0;
}