#include <bits/stdc++.h>
using namespace std;
int T;
int n, m;
int ans = 0x3f3f3f3f;
int vis[20];
bool flag = 0;
int rem;
vector<int> shot, avl;
struct Position
{
    double x, y;
} p[20];

void calc(double x1, double y1, double x2, double y2, double &a, double &b)
{
    a = (x1 * y2 - x2 * y1) / (x1 * x2 * x2 - x1 * x2 * x1);
    b = (y1 - a * x1 * x1) / x1;
    return;
}

void dfs(int bird, int pig)
{
    if (pig <= 0)
    {
        ans = min(ans, bird);
        return;
    }
    if (pig == 1)
    {
        ans = min(ans, bird + 1);
        return;
    }
    if (bird >= ans)
        return;
    avl.clear();
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            avl.push_back(i);
    flag = 0;
    for (auto i : avl)
    {
        double a, b;
        if (p[avl[0]].x == p[i].x)
            continue;
        calc(p[avl[0]].x, p[avl[0]].y, p[i].x, p[i].y, a, b);
        if (a >= 0)
            continue;
        shot.clear();
        rem = pig;
        for (auto j : avl)
        {
            if (abs(p[j].y - (a * p[j].x * p[j].x + b * p[j].x)) <= 1e-7)
            {
                shot.push_back(j);
                vis[j]++;
                rem--;
                flag = 1;
            }
        }
        dfs(bird + 1, rem);
        for (auto j : shot)
            vis[j]--;
    }
    if (!flag)
    {
        vis[avl[0]] = 1;
        dfs(bird + 1, pig - 1);
        vis[avl[0]] = 0;
    }
    ans = min(ans, bird + pig);
    return;
}

int main()
{
    cin >> T;
    while (T--)
    {
        memset(vis, 0, sizeof vis);
        shot.clear(), avl.clear(), flag = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> p[i].x >> p[i].y;
        ans = n;
        dfs(0, n);
        cout << ans << endl;
    }
}