#include <bits/stdc++.h>

using std::numbers::pi;

struct point {
	double x, y;

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

	friend double cross(point p, point q) {
		return p.x * q.y - p.y * q.x;
	}
	friend double dot(point p, point q) {
		return p.x * q.x + p.y * q.y;
	}
	friend double ang(point p, point q) {
		return std::atan2(p.y - q.y, p.x - q.x);
	}
	friend double dis(point p, point q) {
		return std::hypot(p.x - q.x, p.y - q.y);
	}
	friend double dis_sq(point p, point q) {
		return std::pow(p.x - q.x, 2) + std::pow(p.y - q.y, 2);
	}

	friend std::istream &operator>>(std::istream &is, point &p) {
		return is >> p.x >> p.y;
	}
	friend std::ostream &operator<<(std::ostream &os, point p) {
		return os << p.x << ' ' << p.y;
	}
};
struct line {
	point x, y;
	friend double dis_sq(point p, line l) {
		return std::pow(cross(p - l.x, l.y - l.x), 2) / dis_sq(l.x, l.y);
	}
};

void solve() {
	int n, m;
	std::cin >> n >> m;
	std::vector<std::pair<point, double>> a(n);
	for (auto &[p, _] : a) std::cin >> p;

	point cen{0, 0};
	for (auto [p, _] : a) cen = cen + p;
	cen = cen / n;

	auto calc = [&a](point q) {
		double s = 0;
		for (auto [p, _] : a) s += std::pow(dis(p, q) - 1, 2);
		return s;
	};
	double mn = calc(cen);

	for (double delta = .1; delta > 1e-8; delta *= .95) {
		point old = cen;
		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				point cur{old.x + delta * dx, old.y + delta * dy};
				double val = calc(cur);
				if (val < mn) {
					mn = val;
					cen = cur;
				}
			}
		}
	}

	// std::cerr << std::fixed << std::setprecision(10) << dis(cen, point{0, 0}) << '\n';
	
	for (auto &[p, g] : a) g = ang(p, cen);
	std::sort(a.begin(), a.end(), [](auto p, auto q) {
		return p.second < q.second;
	});

	auto b = a;
	std::sort(b.begin(), b.end(), [cen](auto p, auto q) {
		return dis(p.first, cen) > dis(q.first, cen);
	});
	int lim = std::min(n, 20), delta = std::min(n - 1, 1);
	std::vector<double> can;
	can.reserve(lim * (delta + 1 + delta));
	for (int i = 0; i < lim; i++) {
		double g = b[i].second;
		for (int d = -delta; d <= delta; d++) {
			can.push_back(g + (1. * d / n) * (2 * pi));
		}
	}

	double best = 1e18;
	int ans = -1;

	for (int num = std::max(3, m - 5); num <= m; num++) {
		for (double g : can) {
			double sum = 0;

			std::vector<std::pair<point, double>> ver(num);
			for (int i = 0; i < num; i++) {
				double cur = g + (1. * i / num) * (2 * pi);
				ver[i].first = point{cen.x + std::cos(cur), cen.y + std::sin(cur)};
				ver[i].second = ang(ver[i].first, cen);
			}
			std::sort(ver.begin(), ver.end(), [](auto p, auto q) {
				return p.second < q.second;
			});

			std::vector<line> edge(num);
			for (int i = 0; i < num; i++) {
				int j = i == 0 ? num - 1 : i - 1;
				edge[i] = {ver[j].first, ver[i].first};
			}

			int pos = 0;
			for (auto [p, x] : a) {
				while (pos != num && ver[pos].second < x) pos++;
				int i = pos == num ? 0 : pos;
				sum += dis_sq(p, edge[i]);
				if (sum >= best) break;
			}

			if (sum < best) {
				best = sum;
				ans = num;
			}
		}
	}

	std::cout << ans << '\n';
}

int main() {
	// freopen("gen.in", "r", stdin);
	// freopen("gen.out", "w", stdout);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	std::cin >> t;
	while (t--) solve();
}