#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int min(int x,int y)
{
  if(x<=y)  return x;
  else  return y;
}
bool check(double x,double y)
{
  if(abs(x-y)<0.000000001)  return true;
  else  return false;
}
int t,n,m;
int g[30][30],f[1<<20];
double x[30],y[30],a[30][30],b[30][30];
int main()
{
  freopen("angrybirds.in","r",stdin);freopen("angrybirds.out","w",stdout);
  scanf("%d",&t);
  while(t--)
  {
    memset(g,0,sizeof(g));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
      scanf("%lf%lf",&x[i],&y[i]);
    for(int i=1;i<=n;++i)
      for(int j=i+1;j<=n;++j)
      {
        if(x[i]==x[j])
        {
          a[i][j]=5;
          continue;
        }
        if(check(y[i]/x[i],y[j]/x[j]))
        {
          a[i][j]=5;
          continue;
        }
        a[i][j]=y[i]/(x[i]*(x[i]-x[j]))-y[j]/(x[j]*(x[i]-x[j]));
        b[i][j]=(x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
        for(int k=1;k<=n;++k)
          if(check(a[i][j]*x[k]*x[k]+b[i][j]*x[k],y[k]))
            g[i][j]=g[i][j]|(1<<(k-1));
      }
    f[0]=0;
    for(int i=0;i<(1<<n);++i)
      for(int j=1;j<=n;++j)
        for(int k=j+1;k<=n;++k)
        {
          if(a[j][k]>-0.00000001)
          {
            f[i]=min(f[i],f[i&(~g[j][k])]+2);
            continue;
          }
          f[i]=min(f[i],f[i&(~g[j][k])]+1);
        }
    printf("%d\n",f[(1<<n)-1]);
  }
  return 0;
}