#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;
const int MAXN = 18 + 3;
const int MAXS = (1 << (MAXN + 1));
const double EPS = 1e-6; // 精度搞的高一点
struct Point {
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
} a[MAXN];
inline bool dcmp (double x) {
    return fabs(x) <= EPS;
}
inline bool dcmp (double x, double y) {
    return dcmp(x - y);
} // 处理浮点数时常用的根据 EPS 判断相等的技巧
struct Line {
    double a, b;
    bool valid;
    unsigned int kill;
    Line(unsigned int kill = 0): a(0), b(0), valid(true), kill(kill) {}
    bool operator<(const Line &other) const {
        return kill > other.kill;
    }
    bool operator==(const Line &other) const {
        return kill == other.kill;
    }
} lines[MAXN * MAXN];
struct Node {
    bool vis;
    int dist;
} N[MAXS];
int n, cmd, limit, lineCnt;
inline int bfs (int status) {
    if (!status) return 0;
    queue<int> q;
    q.push(status);
    N[status].vis = true;
    N[status].dist = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (N[v].dist == limit) continue;
        for (int i = 1; i <= lineCnt; i++) {
            Line &l = lines[i];
            if (l.valid && (l.kill & status)) {
                int u = v;
                u &= ~l.kill; // 状压通过位运算搞掉
                if (!N[u].vis) {
                    N[u].vis = true;
                    N[u].dist = N[v].dist + 1;
                    if (!u) return N[u].dist;
                    q.push(u);
                }
            }
        }
    }
    return n;
}
inline Line getLine (const Point &a, const Point &b) {
    Line l;
    l.a = (a.x * b.y - b.x * a.y) / (a.x * b.x * b.x - b.x * a.x * a.x);
    l.b = (a.y - l.a * a.x * a.x) / a.x;
    return l;
}
inline bool onLine (const Line &l, const Point &a) {
    return dcmp(l.a * a.x * a.x + l.b * a.x, a.y);
}
inline int solve () {
    bool flags[MAXN];
    for (int i = 1; i <= n; i++) flags[i] = false;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (dcmp(a[i].x, a[j].x)) continue;
            Line l = getLine(a[i], a[j]);
            if (l.a >= 0) continue;
            flags[i] = flags[j] = true;
            lines[++lineCnt] = l;
        }
    }
    for (int i = 1; i <= lineCnt; i++) {
        for (int j = 1; j <= n; j++) {
            if (onLine(lines[i], a[j])) {
                lines[i].kill |= (1u << (j - 1));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!flags[i]) {
            lines[++lineCnt] = Line(1u << (i - 1)); // 或运算标记能击杀的猪的编号
        }
    }
    sort(lines + 1, lines + lineCnt + 1);
    for (int i =  1; i <= lineCnt; i++) {
        for (int j = i + 1; j <= lineCnt; j++) {
            if ((lines[i].kill | lines[j].kill) == lines[i].kill) {
                lines[j].valid = false;
            } // 如果抛物线i能击杀抛物线j能击杀的所有猪，而且能击杀抛物线j不能击杀的猪，则使用抛物线j明显不优
        }
    }
    for (unsigned int i = 0; i < (1u << n); i++) {
        N[i].vis = false;
    }
    return bfs((1u << n) - 1);
}
int main() {
    freopen("angrybirds.in", "r", stdin);
    freopen("angrybirds.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &cmd);
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf", &a[i].x, &a[i].y);
        }
        lineCnt = 0;
        if (cmd == 1) {
            limit = ceil(double(n) / 3 + 1);
        } else {
            limit = n;
        }
        printf("%d\n", solve());
    }
    fclose(stdin);
    fclose(stdout);
}