#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

#define double long double

const int maxn = 1010;
const double pi = acosl(-1.);

struct Complex {
  double a, b; // a + bi
  Complex() { }
  Complex(double x, double y) { a = x, b = y; }
  friend Complex operator+(Complex x, Complex y) { return Complex(x.a + y.a, x.b + y.b); }
  friend Complex operator-(Complex x, Complex y) { return Complex(x.a - y.a, x.b - y.b); }
  friend Complex operator*(Complex x, Complex y) { return Complex(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a); }
} w[maxn][maxn];

double pw(double x) { return x * x; }

struct point {
  double x, y;
  point() { }
  point(double a, double b) { x = a, y = b; }
  friend point operator-(point x, point y) { return point(x.x - y.x, x.y - y.y); }
  friend double operator*(point x, point y) { return x.x * y.y - x.y * y.x; }
} a[maxn];

point spin(point x, double a) {
  return point(x.x * cosl(a) - x.y * sinl(a), x.x * sinl(a) + x.y * cosl(a));
}

int n, k, p[maxn];
double val[maxn], cur[maxn];
point b[maxn], c[maxn];
vector<double> theta;

double getsum(double x, double y) {
  double sum = 0;
  rep (i, 1, n) cur[i] = pw(1. - sqrtl(pw(x - a[i].x) + pw(y - a[i].y)));
  rep (i, 1, n) sum += cur[i];
  return sum;
}

const double eps = 1e-6;

point getO() {
  double x = 0, y = 0;
  for (double d = 1; d >= 1e-5; d *= .5) {
    double nx = x, ny = y, cur = getsum(x, y);
    rep (o0, -1, 1) rep (o1, -1, 1) {
      double tmp = getsum(x + o0 * d, y + o1 * d);
      if (tmp < cur) cur = tmp, nx = x + o0 * d, ny = y + o1 * d;
    }
    x = nx, y = ny;
  }
  return point(x, y);
}

double calc(point p, point q, point x) {
  return pw((p - x) * (q - x)) / (pw(p.x - q.x) + pw(p.y - q.y));
}

void work() {
  cin >> n >> k;
  rep (i, 1, n) cin >> a[i].x >> a[i].y;
  point O = getO();
  rep (i, 1, n) a[i].x -= O.x, a[i].y -= O.y;
  sort(a + 1, a + n + 1, [&](point x, point y) {
    return atan2l(x.y, x.x) < atan2l(y.y, y.x);
  });
  rep (i, 1, n) p[i] = i;
  sort(p + 1, p + n + 1, [&](int x, int y) {
    return pw(a[x].x) + pw(a[x].y) > pw(a[y].x) + pw(a[y].y);
  });
  theta.clear();
  rep (i, 1, min(n, 10)) theta.emplace_back(atan2l(a[p[i]].y, a[p[i]].x));
  double mn = 1e18;
  int ans = 0;
  rep (m, max(3, k - 5), k) {
    val[m] = 1e18;
    for (double the : theta) {
      rep (i, 1, m) b[i] = spin(point(w[m][i - 1].a, w[m][i - 1].b), the);
      int mnp = 1;
      rep (i, 1, m) if (atan2l(b[i].y, b[i].x) < atan2l(b[mnp].y, b[mnp].x)) mnp = i;
      rep (i, 1, m) c[i] = b[(mnp + i - 2) % m + 1];
      rep (i, 1, m) b[i] = c[i];
      double sum = 0;
      int pos = 1;
      rep (i, 1, n) {
        while (pos <= m && atan2l(b[pos].y, b[pos].x) < atan2l(a[i].y, a[i].x)) pos++;
        int pre = (pos == 1 ? m : pos - 1);
        if (pos > m) pre = m;
        sum += calc(b[pos > m ? 1 : pos], b[pre], a[i]);
      }
      chkmn(val[m], sum);
    }
    if (val[m] < mn) mn = val[m], ans = m;
  }
  cout << ans << '\n';
}

int main() {
  rep (m, 3, 30) {
    w[m][0] = Complex(1, 0);
    Complex e = Complex(cosl(2 * pi / m), sinl(2 * pi / m));
    rep (i, 1, m - 1) w[m][i] = w[m][i - 1] * e;
  }
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}