#include<bits/stdc++.h>
using namespace std;
int e[2000000];
bool f[2000000];
long long a1,a2,xx[2000],yy[2000],a_fenmu,a_fenzi,b_fenmu,b_fenzi,aa,bb,cc,dd,ee,ff;
int k,T,n,m,i,j,ans;
double xxx,yyy;
long long gcd(long long x,long long y)
{
if (y==0) return x;
long long ans=gcd(y,x % y);
return ans;
}
int main()
{
    cin>>T;
    for (;T;T--)
         {
             cin>>n>>m;
             for (i=0;i<(1<<n);i++) 
                   { 
                    f[i]=0;e[i]=10000000;
                   }
            e[0]=0;
             for (i=1;i<=n;i++) 
                  {
                  cin>>xxx>>yyy;
                  xx[i]=(int)(xxx*100);
                  yy[i]=(int)(yyy*100);
                  }
             for (i=1;i<=n;i++)
                {
                    for (j=1;j<i;j++)
                        {
                            ans=0;
                            aa=xx[i]*xx[i];bb=xx[i];cc=yy[i];
                            dd=xx[j]*xx[j];ee=xx[j];ff=yy[j];
                            a_fenzi=cc*ee-bb*ff;a_fenmu=aa*ee-bb*dd;
                            b_fenzi=cc*dd-aa*ff;b_fenmu=bb*dd-aa*ee;
                            if (((a_fenzi<0)&(a_fenmu>0))||((a_fenzi>0)&(a_fenmu<0)))
                                 {
                                 a1=abs(a_fenzi);a2=abs(a_fenmu);a1=gcd(a1,a2);
                                 a_fenzi/=a1;a_fenmu/=a1;
                            for (k=1;k<=n;k++)
                               if ((xx[k]*xx[k])*b_fenmu*a_fenzi+(xx[k])*a_fenmu*b_fenzi==yy[k]*a_fenmu*b_fenmu)
                                     ans|=(1<<(k-1));
                            if (f[ans]==false)
                                {
                                    f[ans]=true;
                                    for (k=0;k<(1<<n);k++)
                                        e[k|ans]=min(e[k|ans],e[k]+1);
                                }
                            }
                        }
                ans=1<<(i-1);
                 for (k=0;k<(1<<n);k++)
                                        e[k|ans]=min(e[k|ans],e[k]+1);
                }
        cout<<e[(1<<n)-1]<<endl;
         }
    return 0;
}