#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; }
} 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];
vector<double> theta;

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

point getO() {
  double x = 0, y = 0;
  rep (i, 1, 3) {
    double l = -1, r = 1;
    rep (_, 1, 20) {
      double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
      if (getsum(m1, y) < getsum(m2, y)) r = m2;
      else l = m1;
    }
    x = (l + r) * .5;
    l = -1, r = 1;
    rep (_, 1, 20) {
      double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
      if (getsum(x, m1) < getsum(x, m2)) r = m2;
      else l = m1;
    }
    y = (l + r) * .5;
  }
  return point(x, y);
}

double calc(point x, int n) {
  double res = 1e18;
  rep (i, 1, n) {
    point p = b[i], q = b[i % n + 1];
    double a = p.y - q.y, b = q.x - p.x;
    double c = 0 - a * p.x - b * p.y;
    chkmn(res, pw(a * x.x + b * x.y + c) / (pw(a) + pw(b)));
  }
  return res;
}

void work() {
  cin >> n >> k;
  rep (i, 1, n) cin >> a[i].x >> a[i].y;
  point O = getO();
  cerr << O.x << " " << O.y << endl;
  rep (i, 1, n) a[i].x -= O.x, a[i].y -= O.y;
  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, 30)) 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);
      double sum = 0;
      rep (i, 1, n) sum += calc(a[i], m);
      chkmn(val[m], sum);
    }
    // cerr << val[m] << endl;
    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();
}