#include <bits/stdc++.h>
using namespace std;
vector<int> e[200005];
int deg[200005], DEG[200005], vis[200005];
set<pair<int, int> > s;
int main(int argc, char** argv) {
  int T;
  cin >> T;
  while (T--) {
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) deg[i] = DEG[i] = vis[i] = 0, e[i].clear();
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      ++deg[u], ++deg[v];
      e[u].push_back(v), e[v].push_back(u);
    }
    if (k == 1) {
      cout << n - 1 << "\n";
      continue;
    }
    for (int i = 1; i <= n; i++) DEG[i] = deg[i];
    for (int i = 1; i <= n; i++) {
      if (deg[i] == 1) {
        for (auto v : e[i]) --DEG[v];
      }
    }
    for (int i = 1; i <= n; i++)
      if (DEG[i] <= 1 && deg[i] > 1)
        s.insert({(deg[i] - DEG[i]) % k, i}), vis[i] = 1;
    while (!s.empty()) {
      int x = (*s.begin()).second;
      s.erase(s.begin());
      ans += (deg[x] - DEG[x]) / k;
      if ((deg[x] - DEG[x]) % k == 0) {
        for (auto v : e[x]) {
          if (s.find({(deg[v] - DEG[v]) % k, v}) != s.end())
            s.erase({(deg[v] - DEG[v]) % k, v}),
                s.insert({(deg[v] - DEG[v] + 1) % k, v});
          --DEG[v];
          if (DEG[v] <= 1 && !vis[v] && deg[v] > 1)
            s.insert({(deg[v] - DEG[v]) % k, v}), vis[v] = 1;
        }
      }
    }
    for (int i = 1; i <= n; i++)
      if (!vis[i] && deg[i] > 1) ans += (deg[i] - DEG[i]) / k;
    for (int i = 1; i <= n; i++) {
    }
    cout << ans << "\n";
  }
  return 0;
}
