#include <bits/stdc++.h>
using namespace std;
class FRemovingLeaves {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int t;
    in >> t;
    while (t--) {
      int n, k;
      in >> n >> k;
      vector<vector<int>> adjs(n + 1);
      vector<int> deg(n + 1), removed_leaves_cnt(n + 1);
      vector<bool> removed(n + 1, false);
      queue<int> qu;
      for (int i = 0; i < n - 1; ++i) {
        int a, b;
        in >> a >> b;
        adjs[a].push_back(b);
        adjs[b].push_back(a);
        deg[a]++;
        deg[b]++;
      }
      for (int i = 1; i <= n; ++i) {
        if (deg[i] == 1) qu.push(i);
      }
      int res = 0;
      while (qu.size()) {
        auto u = qu.front();
        qu.pop();
        removed[u] = true;
        for (const auto& adj : adjs[u]) {
          if (!removed[adj]) {
            deg[adj]--;
            removed_leaves_cnt[adj]++;
            if (removed_leaves_cnt[adj] % k == 0) {
              res++;
              if (deg[adj] == 1) qu.push(adj);
            }
          }
        }
      }
      out << res << endl;
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  FRemovingLeaves solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
