#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(nullptr));
vector<complex<double>> gen(int n){
  uniform_real_distribution<double> dis_0(-1, 1);
  uniform_real_distribution<double> dis_alpha(0, 2 * numbers::pi_v<double> / n);
  uniform_int_distribution<int> dis_n(0, n - 1);
  uniform_real_distribution<double> dis(-sin(numbers::pi_v<double> / n), sin(numbers::pi_v<double> / n));
  normal_distribution<double> dis_err(0, 0.01);
  double x_0 = dis_0(rnd), y_0 = dis_0(rnd), alpha = dis_alpha(rnd);
  constexpr int N = 1000; vector<complex<double>> res;
  for(int i = 0; i < N; i++){
    double x = dis(rnd), y = cos(numbers::pi_v<double> / n);
    auto tmp = complex<double>(x, y) * exp(1i * (2 * numbers::pi_v<double> / n * dis_n(rnd) + alpha));
    res.push_back(tmp + complex<double>(dis_err(rnd) + x_0, dis_err(rnd) + y_0));
  }
  return res;
}
double calc(vector<complex<double>> A){
  complex<double> O;
  for(auto P: A) O += P;
  O /= A.size(); double res = 0;
  for(auto P: A) res += (pow(abs(P - O), 2));
  return res;
}
constexpr double X[] = {600, 700, 800, 850, 885, 910, 926};
int main(){
  int _;
  for(cin >> _; _--;){
    int n, m; cin >> n >> m;
    vector<complex<double>> a;
    while(n--){double x, y; cin >> x >> y, a.push_back(x + 1i * y);}
    double res = calc(a);
    while(m > 3 && res < X[m - 4]) m--;
    cout << m << '\n';
  }
  return 0;
  for(int k = 3; k <= 30; k++){
    double mx = -INFINITY, mn = INFINITY;
    for(int i = 1; i <= 300; i++){double x = calc(gen(k)); mx = max(mx, x), mn = min(mn, x);}
    cout << k << ':' << mn << '~' << mx << endl;
  }
  return 0;
}