#include <bits/stdc++.h>
using namespace std;
set<int> shob[200005], leafs[200005];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) shob[i].clear(), leafs[i].clear();
    for (int i = 1; i < n; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      shob[u].insert(v);
      shob[v].insert(u);
    }
    for (int i = 1; i <= n; i++) {
      for (int v : shob[i]) {
        if (shob[v].size() == 1) leafs[i].insert(v);
      }
    }
    set<pair<int, int> > se;
    for (int i = 1; i <= n; i++) se.insert({-leafs[i].size(), i});
    int ans = 0;
    while (se.size()) {
      pair<int, int> p = *se.begin();
      se.erase(se.begin());
      int u = p.second;
      if (leafs[u].size() < k) break;
      int ald = 0;
      for (auto it = leafs[u].begin(); ald < k; it = leafs[u].erase(it)) {
        int v = *it;
        se.erase({-leafs[v].size(), v});
        shob[u].erase(v);
        ald++;
      }
      se.insert({-leafs[u].size(), u});
      if (shob[u].size() == 1) {
        int v = *shob[u].begin();
        se.erase({-leafs[v].size(), v});
        leafs[v].insert(u);
        se.insert({-leafs[v].size(), v});
      }
      ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}
