#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
int Q, n, m, ans, tot, rt, head[N], deg[N], f[N];
struct edge {
  int next, to;
} e[N];
void add(int from, int to) {
  e[++tot].to = to;
  e[tot].next = head[from];
  head[from] = tot;
}
int dfs(int x, int fa) {
  int cnt = 0, sum = 0;
  for (int i = head[x]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      cnt += dfs(v, x);
      sum++;
    }
  }
  ans += cnt / m;
  return (cnt % m == 0) && (sum == cnt);
}
void topsort() {
  queue<int> q;
  for (int i = 1; i <= n; i++)
    if (deg[i] == 1) q.push(i);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = e[i].next) {
      int v = e[i].to;
      if (deg[v] > 0) {
        deg[v]--;
        deg[u]--;
        f[v]++;
        if (f[v] == m) {
          f[v] = 0;
          ans++;
        }
        if (deg[v] == 1 && !f[v]) {
          q.push(v);
        }
      }
    }
  }
}
int main() {
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) head[i] = -1, deg[i] = f[i] = 0;
    for (int i = 1, x, y; i < n; i++) {
      scanf("%d%d", &x, &y);
      add(x, y);
      add(y, x);
      deg[x]++;
      deg[y]++;
      if (deg[x] > 1) rt = x;
      if (deg[y] > 1) rt = y;
    }
    ans = 0;
    topsort();
    printf("%d\n", ans);
  }
  return 0;
}
