#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

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

int n, m;
PDD q[N];
int path[N][N];  // path(i, j) 穿过点i 和 j的抛物线能穿过哪些点，
int f[M];  // f[i]: i这种覆盖情况需要的小鸟数


int cmp(double x1, double x2){
    if(fabs(x1 - x2) < eps) return 0;  // 误差小于1e-8可以认为相等
    if(x1 < x2) return -1;
    else return 1;
}

int main(){
    int T;
    cin >> T;

    while(T --){
        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,i)的抛物线一定能穿过(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)) continue;
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                if(cmp(a, 0) >= 0) continue;  // 抛物线一定是开口向下的抛物线，如果a大于0，证明这两点组成的抛物线是不合法的
                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)) state += 1 << k;  // 第k个点在抛物线覆盖范围内
                }
                path[i][j] = state;  // 两个点才能确定一条唯一的抛物线
            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        // dp过程
        // i是取不到全为1的情况因为这种情况就不用更新了，直接跳出，已经全覆盖了
        for (int i = 0; i + 1 < 1 << n; i ++){
            int x = 0;  // x代表没有覆盖的列
            for(int j = 0; j < n; j ++){
                if(!(i >> j & 1)){  // 如果没有覆盖的话
                    x = j;  
                    break;
                }
            }

            for(int j = 0; j < n; j ++){  // 枚举所有可以覆盖x的抛物线
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);  // 更新新状态 i|path 需要的最小抛物线数量
            }
        }

        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}