#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2> p) {
  out << '(' << p.first << ',' << p.second << ')';
  return out;
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <class T>
istream& operator>>(istream& in, vector<T>& v) {
  for (T& x : v) in >> x;
  return in;
}
template <class T>
ostream& operator<<(ostream& out, const vector<vector<T>>& v) {
  for (const vector<T>& x : v) out << x << '\n';
  return out;
}
template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  for (const T& x : v) out << x << ' ';
  return out;
}
long long gcd(long long a, long long b) {
  if (b > a) swap(a, b);
  return (b ? gcd(b, a % b) : a);
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
const int h = 1000000007;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cerr.setstate(ios::failbit);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vvi MM(n);
    vector<set<int>> M(n);
    vi deg(n);
    for (int i = (0); i < (n - 1); i++) {
      int x, y;
      cin >> x >> y;
      x--, y--;
      MM[x].push_back(y);
      MM[y].push_back(x);
      deg[x]++, deg[y]++;
    }
    priority_queue<pii> pq;
    for (int i = (0); i < (n); i++) {
      if (deg[i] == 1) {
        int x = *MM[i].begin();
        M[x].insert(i);
        pq.push({M[x].size(), x});
      }
    }
    int ans = 0;
    while (!pq.empty()) {
      int d = pq.top().first;
      int x = pq.top().second;
      pq.pop();
      if (M[x].size() != d) continue;
      if (d < k) break;
      ans += M[x].size() / k;
      int to_remove = M[x].size() / k * k;
      while (to_remove) {
        int z = *M[x].begin();
        M[x].erase(z);
        M[z].erase(x);
        deg[x]--, deg[z]--;
        to_remove--;
      }
      if (deg[x] == 1) {
        for (int y : MM[x]) {
          if (deg[y] == 0) continue;
          M[y].insert(x);
          pq.push({M[y].size(), y});
        }
      }
    }
    cout << ans << '\n';
  }
}
