#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> h[N];
int st[N], sz[N];
bool vis[N];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      st[u]++;
      st[v]++;
      h[u].push_back(v);
      h[v].push_back(u);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
      if (st[i] == 1) q.push(i);
    int ans = 0;
    while (q.size()) {
      int t = q.front();
      q.pop();
      vis[t] = true;
      for (int it : h[t]) {
        if (vis[it]) continue;
        st[it]--;
        sz[it]++;
        if (sz[it] % k == 0) {
          ans++;
          if (st[it] == 1) q.push(it);
        }
      }
    }
    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
      h[i].clear();
      st[i] = sz[i] = vis[i] = 0;
    }
  }
  return 0;
}
