#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream& operator>>(istream& in, vector<T>& a) {
  for (auto& i : a) in >> i;
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T>& a) {
  for (auto& i : a) out << i << " ";
  return out;
}
template <typename T, typename U>
void chkmin(T& a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
void chkmax(T& a, U b) {
  if (a < b) a = b;
}
void solve() {
  int n, k;
  cin >> n >> k;
  vector<set<int>> gr(n);
  for (int i = (int)1; i < (int)n; i++) {
    int v, u;
    cin >> v >> u, --v, --u;
    gr[v].insert(u), gr[u].insert(v);
  }
  auto is_leaf = [&](int v) { return gr[v].size() == 1; };
  vector<int> cnt(n);
  vector<bool> used(n);
  set<int> good;
  for (int i = (int)0; i < (int)n; i++) {
    for (int j : gr[i]) cnt[i] += is_leaf(j);
    if (cnt[i] % k == 0 && cnt[i] > 0) {
      good.insert(i);
    }
  }
  int ans = 0;
  while (!good.empty()) {
    int v = *good.begin();
    good.erase(good.begin());
    vector<int> leaves;
    for (int u : gr[v])
      if (is_leaf(u)) leaves.push_back(u);
    for (int u : leaves) {
      gr[v].erase(u);
      gr[u].clear();
    }
    ans += (int)(leaves).size() / k;
    if (is_leaf(v)) {
      for (int u : gr[v]) {
        cnt[u]++;
        if (good.find(u) != good.end() && cnt[u] % k) good.erase(u);
        if (cnt[u] > 0 && cnt[u] % k == 0) {
          good.insert(u);
        }
      }
    }
  }
  for (int i = (int)0; i < (int)n; i++) {
    int cur = 0;
    for (int j : gr[i]) cur += is_leaf(j);
    ans += cur / k;
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t-- > 0) solve();
  return 0;
}
