#include <bits/stdc++.h>
int main() {
  int32_t num_tests;
  std::cin >> num_tests;
  for (int32_t t = 0; t < num_tests; t++) {
    int32_t n, k;
    std::cin >> n >> k;
    std::set<int32_t>* tree = new std::set<int32_t>[n];
    for (int32_t i = 0; i < n - 1; i++) {
      int32_t src, dst;
      std::cin >> src >> dst;
      src--;
      dst--;
      tree[src].insert(dst);
      tree[dst].insert(src);
    }
    if (k == 1) {
      std::cout << n - 1 << "\n";
      continue;
    }
    int32_t* degrees = new int32_t[n];
    std::vector<int32_t>* attached_leaves = new std::vector<int32_t>[n];
    for (int32_t i = 0; i < n; i++) {
      degrees[i] = tree[i].size();
      for (auto it = tree[i].begin(); it != tree[i].end(); it++)
        if (tree[*it].size() == 1) attached_leaves[i].push_back(*it);
    }
    std::set<int32_t> active;
    int32_t answer = 0;
    for (int32_t i = 0; i < n; i++)
      if (attached_leaves[i].size() >= k) active.insert(i);
    while (!active.empty()) {
      int32_t v = *active.begin();
      active.erase(active.begin());
      int32_t erased_blocks = attached_leaves[v].size() / k;
      answer += erased_blocks;
      for (int32_t i = 0; i < erased_blocks * k; i++) {
        tree[v].erase(attached_leaves[v].back());
        attached_leaves[v].pop_back();
      }
      degrees[v] -= erased_blocks * k;
      if (degrees[v] == 1) {
        attached_leaves[*tree[v].begin()].push_back(v);
        if (attached_leaves[*tree[v].begin()].size() >= k)
          active.insert(*tree[v].begin());
      }
    }
    std::cout << answer << "\n";
  }
  return 0;
}
