#include <bits/stdc++.h>
using namespace std;
const int maxx = 600010;
int t, n, m, k, u, v;
int ans = 0, total = 0, sum = 0, cnt = 0;
vector<set<int> > g;
vector<set<int> > leaf;
struct node {
  bool operator()(const int x, const int y) const {
    if (leaf[x].size() == leaf[y].size()) return x < y;
    return leaf[x].size() > leaf[y].size();
  }
};
int main() {
  scanf("%d", &t);
  while (t--) {
    ans = 0;
    scanf("%d%d", &n, &k);
    g = leaf = vector<set<int> >(n);
    for (register int i = 0; i < n; i++) g[i].clear(), leaf[i].clear();
    for (register int i = 1; i < n; i++) {
      scanf("%d%d", &u, &v);
      u--, v--;
      g[u].insert(v);
      g[v].insert(u);
    }
    for (register int i = 0; i < n; i++)
      if (g[i].size() == 1) leaf[*g[i].begin()].insert(i);
    set<int, node> s;
    set<int>::iterator it;
    for (register int i = 0; i < n; i++) s.insert(i);
    while (!s.empty()) {
      int u = *s.begin();
      if (leaf[u].size() < k) break;
      int opt = leaf[u].size();
      for (register int i = 0; i < k; i++) {
        int v = *leaf[u].begin();
        g[u].erase(v), g[v].erase(u);
        s.erase(u), s.erase(v);
        leaf[u].erase(v);
        if (leaf[v].count(u)) leaf[v].erase(u);
        if (g[u].size() == 1) {
          int w = *g[u].begin();
          s.erase(w);
          leaf[w].insert(u);
          s.insert(w);
        }
        s.insert(u), s.insert(v);
      }
      ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}
