#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = N << 1;
int n, k;
int g[N], e[M], ne[M], idx;
int deg[N], ldeg[N];
int q[M << 1], hh, tt;
void init() {
  memset(g, -1, (n + 1) * sizeof(int));
  memset(deg, 0, (n + 1) * sizeof(int));
  memset(ldeg, 0, (n + 1) * sizeof(int));
  idx = 0;
  hh = tt = 0;
}
void add_edge(int u, int v) {
  e[idx] = v;
  ne[idx] = g[u];
  g[u] = idx++;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    init();
    for (int i = 0; i < n - 1; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      add_edge(u, v);
      add_edge(v, u);
      deg[u]++;
      deg[v]++;
    }
    if (k == 1) {
      printf("%d\n", n - 1);
      continue;
    }
    for (int u = 1; u <= n; ++u) {
      for (int i = g[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (deg[v] == 1) ldeg[u]++;
      }
      if (ldeg[u] >= k) q[tt++] = u;
    }
    int ans = 0;
    while (hh < tt) {
      int u = q[hh++];
      deg[u] -= k;
      ldeg[u] -= k;
      ans++;
      if (ldeg[u] >= k) q[tt++] = u;
      if (deg[u] == 1 && ldeg[u] == 0) {
        for (int i = g[u]; ~i; i = ne[i]) {
          int v = e[i];
          ldeg[v]++;
          if (ldeg[v] == k) q[tt++] = v;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
