#include <bits/stdc++.h>
using namespace std;
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long fexp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 1000000007;
    b /= 2;
    a = a * a % 1000000007;
  }
  return ans;
}
long long inverse(long long a, long long p) { return fexp(a, p - 2); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long T;
  cin >> T;
  long long t = 0;
  while (t++ < T) {
    long long n, k;
    cin >> n >> k;
    set<long long> adj[n];
    vector<long long> deg(n, 0);
    for (long long i = 0; i < n - 1; i++) {
      long long x, y;
      cin >> x >> y;
      x--;
      y--;
      adj[x].insert(y);
      adj[y].insert(x);
      deg[x]++;
      deg[y]++;
    }
    vector<long long> le;
    long long ans = 0;
    for (long long i = 0; i < n; i++)
      if (deg[i] == 1) le.push_back(i);
    vector<long long> cnt(n, 0);
    for (long long i = 0; i < (long long)(le).size(); i++) {
      long long u = le[i];
      if (deg[u] < 1 || adj[u].size() == 0) continue;
      if (!(deg[u] == 1 && adj[u].size() == 1)) continue;
      long long p = *adj[u].begin();
      adj[p].erase(u);
      cnt[p]++;
      if (cnt[p] == k) {
        cnt[p] = 0;
        ans++;
        deg[p] -= k;
      }
      if (deg[p] == 1 && cnt[p] == 0) le.push_back(p);
    }
    cout << ans << endl;
  }
  return 0;
}
