#include <bits/stdc++.h>
using namespace std;
set<int> vi[200200];
int leaf[200200], edge[200200];
void removeEdge(int curr, int take) {
  vector<int> to;
  for (auto x : vi[curr]) {
    if (edge[x] == 1 && take > 0) {
      to.push_back(x);
      take--;
    }
  }
  for (auto x : to) {
    vi[curr].erase(x);
    vi[x].erase(curr);
  }
}
int main() {
  int n, i, j, k, x, y, ans, curr, temp, m;
  int tc;
  cin >> tc;
  while (tc--) {
    scanf("%d %d", &n, &k);
    for (i = 1; i <= n; i++) edge[i] = 0, leaf[i] = 0, vi[i].clear();
    for (i = 1; i < n; i++) {
      scanf("%d %d", &x, &y);
      edge[x]++;
      edge[y]++;
      vi[x].insert(y);
      vi[y].insert(x);
    }
    for (i = 1; i <= n; i++) {
      if (edge[i] == 1) {
        leaf[*vi[i].begin()]++;
      }
    }
    set<pair<int, int>, greater<pair<int, int> > > s;
    for (i = 1; i <= n; i++) {
      s.insert({leaf[i], i});
    }
    ans = 0;
    while (!s.empty()) {
      curr = (*s.begin()).second;
      s.erase(s.begin());
      if (leaf[curr] < k || s.empty()) break;
      int take = leaf[curr] / k;
      ans += take;
      leaf[curr] = leaf[curr] % k;
      edge[curr] -= take * k;
      removeEdge(curr, take * k);
      if (edge[curr] == 1) {
        int to = *vi[curr].begin();
        s.erase({leaf[to], to});
        leaf[to]++;
        s.insert({leaf[to], to});
      } else {
        if (edge[curr] == 0) continue;
        s.insert({leaf[curr], curr});
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
