#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    int n, k;
    cin >> n >> k;
    vector<set<int>> edge(n);
    vector<set<int>> leaf(n);
    int a, b;
    for (int i = 1; i < n; ++i) {
      cin >> a >> b;
      a--;
      b--;
      edge[a].insert(b);
      edge[b].insert(a);
    }
    vector<bool> isleaf(n, 0);
    for (int i = 0; i < n; ++i) {
      if (edge[i].size() == 1) isleaf[i] = 1;
    }
    map<int, set<int>> leafnum;
    for (int i = 0; i < n; ++i) {
      for (int u : edge[i]) {
        if (isleaf[u]) {
          leaf[i].insert(u);
        }
      }
      if (leaf[i].size() != 0) leafnum[leaf[i].size()].insert(i);
    }
    int ans = 0;
    while (!leafnum.empty() && leafnum.rbegin()->first >= k) {
      ans += 1;
      int t = leafnum.rbegin()->first;
      int node = *(leafnum.rbegin()->second.begin());
      leafnum.rbegin()->second.erase(node);
      if (leafnum.rbegin()->second.size() == 0) leafnum.erase(t);
      for (int i = 0; i < k; ++i) {
        int u = *(leaf[node].begin());
        leaf[node].erase(u);
        edge[u].erase(node);
        edge[node].erase(u);
        if (leaf[u].size() != 0) {
          leafnum[leaf[u].size()].erase(u);
          if (leafnum[leaf[u].size()].size() == 0)
            leafnum.erase(leaf[u].size());
        }
      }
      if (edge[node].size() == 1) {
        isleaf[node] = 1;
        for (int u : edge[node]) {
          if (leaf[u].size() != 0) {
            leafnum[leaf[u].size()].erase(u);
            if (leafnum[leaf[u].size()].size() == 0)
              leafnum.erase(leaf[u].size());
          }
          leaf[u].insert(node);
          leafnum[leaf[u].size()].insert(u);
        }
      }
      if (leaf[node].size() != 0) leafnum[leaf[node].size()].insert(node);
    }
    cout << ans << '\n';
  }
}
