/*

n只小猪
f[i]: 打死i这个状态下的每个猪，所需最少的小鸟。---0011，杀死第1只和第2只
path[i][j]: 经过第i只猪和第j只猪的线都能经过经过那几只猪。---path[i][j]=0011,能经过第1只和第2只
PDD q[N]: 存每只猪的位置

转移：枚举每个状态state，
      找到state不能走到的位置x（哪个位置为0）
      枚举path[x][j], 0<j<n。所有能经过x的线
      加进去的状态为 new_state = state | path[x][j]
      f[new_state] = min(f[new_state], f[state] + 1);

*/

include

include

include

include

define x first

define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-8;

int n, m;
PDD q[N];
int pathN;
int f[M];

int cmp(double x, double y)
{
if(fabs(x - y) < eps) return 0;
if(x < y) return -1;
return 1;
}

int main()
{

int tt;
cin >> tt;
while(tt -- )
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        cin >> q[i].x >> q[i].y;

    memset(path, 0, sizeof path);
    for (int i = 0; i < n; i ++ )
    {
        path[i][i] = 1 << i;                // 没有点和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(cmp(x1, x2) == 0) continue;                  // 两点不能竖直存在

            double a = (y1 / x1 - y2 / x2) / (x1 - x2);
            double b = y1 / x1 - a * x1;

            if(cmp(a, 0) >= 0) continue;                    // 抛物线开口只能向下

            int state = 0;
            for (int k = 0; k < n; k ++ )                   // 枚举哪个点能过这个线，就加上
            {
                double x = q[k].x, y = q[k].y;
                if(cmp(a * x * x + b * x, y) == 0)
                    state += 1 << k;
            }
            path[i][j] = state;
        }
    }

    memset(f, 0x3f, sizeof f);
    f[0] = 0;                                   //一个点没经过，需要0条抛物线
    for(int i = 0; i < 1 << n; i ++ )
    {
        int x = 0;
        for(int j = 0; j < n; j ++ )                    // 找到不能经过的点
            if((i >> j & 1) == 0)
            {
                x = j;
                break;
            }

        for(int j = 0; j < n; j ++ )                                // 状态转移
            f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
    }

for(int i = 0; i < 1 << n; i ++ )

{
    int x = 0;
    for(int j = 0; j < n; j ++ )                    // 找到不能经过的点
        if((i >> j & 1) == 0)
        {
            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;                // 111...111 所有点都能经过
}
return 0;

}