#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);
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));
}
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;
	}
	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;
		auto A = a;
		for(int i = 0;i < N;++i) {
			db ra = arg(A[i]);
			cp rr = std::polar(1., -r * floor(ra / r));
			A[i] *= rr;
		}
		cp x[3];
		for(int i : {0, 1, 2})
			x[i] = std::polar(1., r * i);
		auto eval = [&](db a) {
			cp rotate = std::polar(1., a);
			db sum = 0;
			for(int i = 0;i < N;++i) {
				cp t = A[i] * rotate;
				db d = std::min(dist(x[0], x[1], t), dist(x[1], x[2], t));
			//	std::cerr << arg(t) << '\n';
			//	assert(0 <= arg(t) && arg(t) <= r * 2);
				static constexpr db s2 = 0.01 * 0.01;
				sum += - d * d / 2 / s2;
			}
			return sum;
		};
		auto rmax = [&](db l, db r) {
			auto [p, pv] = findmax(l, r, eval);
			return pv;
		};
		db max = -1. / 0;
		const int C = 10;
		for(int i = 0;i < C;++i) {
			max = std::max(max, rmax(r / C * i, r / C * (i + 1)));
		}
		if(max > P) {
			P = max;
			ans = i;
		}
	}
	cout << ans << '\n';
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for(int i = 0;i < T;++i) {
		solve();
	}
}