#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 2;
set<int> v[maxn];
set<int> lf[maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
      v[i].clear();
      lf[i].clear();
    }
    for (int i = 0; i < n - 1; ++i) {
      int a, b;
      cin >> a >> b;
      a--;
      b--;
      v[a].insert(b);
      v[b].insert(a);
    }
    if (k == 1) {
      cout << n - 1 << "\n";
      continue;
    }
    set<pair<int, int> > s;
    for (int i = 0; i < n; ++i) {
      for (int j : v[i]) {
        if (v[j].size() == 1) lf[i].insert(j);
      }
    }
    for (int i = 0; i < n; i++) {
      s.insert(make_pair(lf[i].size(), i));
    }
    int ans = 0;
    while ((*(--s.end())).first >= k) {
      int temp = (*(--s.end())).first;
      int in = (*(--s.end())).second;
      s.erase(make_pair(lf[in].size(), in));
      ans += (temp / k);
      int ct = (temp / k) * k;
      while (ct--) {
        v[in].erase(*(lf[in].begin()));
        lf[in].erase(lf[in].begin());
      }
      if (v[in].size() == 1 && lf[in].size() == 0) {
        int in1 = *(v[in].begin());
        s.erase(make_pair(lf[in1].size(), in1));
        lf[in1].insert(in);
        s.insert(make_pair(lf[in1].size(), in1));
      }
      s.insert(make_pair(lf[in].size(), in));
    }
    cout << ans << "\n";
  }
}
