#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
using cp = std::complex<db>;
const db pi = std::acos(-1), sqrt_pi = std::sqrt(pi);
db dot(const cp & x, const cp & y) {
	return x.real() * y.real() + x.imag() * y.imag();
}
db det(const cp & x, const cp & y) {
	return x.real() * y.imag() - x.imag() * y.real();
}
db dist(const cp & a, const cp & b, const cp & x) {
	if(dot(a - b, x - b) <= 0) return abs(x - b);
	if(dot(b - a, x - a) <= 0) return abs(x - a);
	return fabs(det(a - x, b - x) / abs(a - b));
}
db logdiff(db l, db r) {
	static constexpr db vv = log(0.554);
	db vr = - r * r - log(fabs(r)) + vv;
	db vl = - l * l - log(fabs(l)) + vv;
	return std::max(vl, vr) + log(1 - exp(-fabs(vr - vl)));
}
std::pair<db, db> findmax(db a, db c, auto f) {
	auto g = [&](db l, db r) {
		return l + (r - l) * (std::numbers::phi_v<db> - 1);
	};
	db b = g(a, c), bv = f(b);
	for(int i = 0;i < 20;++i) {
		db x = g(a, b), xv = f(x);
		if(xv > bv) { // change here if findmin
			c = b, b = x, bv = xv;
		} else {
			a = c, c = x;
		}
	}
	return {b, bv};
} // log1.618 (2) ≈ 1.44
void solve() {
	int N, n;
	cin >> N >> n;
	std::vector<cp> a(N);
	cp aver = 0;
	for(int i = 0;i < N;++i) {
		db u, v;
		cin >> u >> v;
		a[i] = cp(u, v);
		aver += a[i];
	}
	aver /= N;
	for(int i = 0;i < N;++i) {
		a[i] -= aver;
	}
	N = 300;
	double P = -1. / 0; int ans = -1;
	for(int i = std::max(3, n - 5);i <= n;++i) {
		db l = 0, r = 2 * pi / i;
		std::vector<cp> B(i);
		for(int j = 0;j < i;++j)
			B[j] = std::polar(1., r * j);
		auto eval = [&](db ang) {
			cp rotate = std::polar(1., ang);
			static constexpr db sig = 0.01, div = 2 * sig * sig;
			db logsum = 0;
			for(int j = 0;j < N;++j) {
				cp o = a[j] * rotate;
				std::vector<db> s(i);
				for(int k = 0;k < i;++k) {
					cp u = B[k], v = B[k == i - 1 ? 0 : k + 1];
					cp t = (v - u) / r;
					u -= o;
					// \int 1/sqrt(2 pi)/sigma e^{-|u + t x|^2/2/sigma^2}
					db A = norm(t) / div, B = 2 * dot(u, t) / div, C = norm(u) / div;
					db sqrt_a = std::sqrt(A);
					// db prod = sqrt_pi / 2 / sqrt_a * exp(B * B / (4 * A) - C);
					db lprod = log(sqrt_pi / 2 / sqrt_a) + (B * B / (4 * A) - C);
					db e0 = (2 * A * r + B) / 2 / sqrt_a;
					db e1 = (2 * A * 0 + B) / 2 / sqrt_a;
					db delta = std::erf(e0) - std::erf(e1);
					if(delta >= 1e-6) {
						s[k] = log(delta) + lprod;
					} else {
						s[k] = logdiff(e0, e1) + lprod;
					}
				}
				db sum = 0;
				iter_swap(s.begin(), max_element(s.begin(), s.end()));
				for(db v : s) sum += exp(v - s[0]);
				logsum += s[0] + log(sum);
				logsum -= log(sig * sqrt(2 * pi)); 
			}
			return logsum;
		};


		auto [p0, max] = findmax(l, r, eval);

		if(max > P) {
			P = max;
			ans = i;
		}
	}
	cout << ans << '\n';
}
int main() {
#ifdef zqj

	freopen("1.in", "r", stdin);
#endif 
	std::ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for(int i = 0;i < T;++i) {
		solve();
	}
}