#include <bits/stdc++.h>
using namespace std;
set<pair<long long, long long> > Set;
set<long long> Set1[250001], Set2[250001];
pair<long long, long long> val, val1;
long long one, two, p[250001], n, i, k, t, val2, ans;
void solve() {
  cin >> n >> k;
  Set.clear();
  for (i = 1; i <= n; i++) {
    p[i] = 0;
    Set1[i].clear();
    Set2[i].clear();
  }
  for (i = 1; i <= n - 1; i++) {
    cin >> one >> two;
    Set1[one].insert(two);
    Set1[two].insert(one);
  }
  for (i = 1; i <= n; i++)
    if (Set1[i].size() == 1) {
      p[*Set1[i].begin()]++;
      Set2[*Set1[i].begin()].insert(i);
    }
  for (i = 1; i <= n; i++) Set.insert(make_pair(p[i], i));
  if (k == 1) {
    cout << n - 1 << '\n';
    return;
  }
  ans = 0;
  while ((*Set.rbegin()).first >= k) {
    ans++;
    val = *Set.rbegin();
    Set.erase(val);
    val.first -= k;
    p[val.second] -= k;
    for (i = 1; i <= k; i++) {
      val2 = *Set2[val.second].begin();
      Set2[val.second].erase(val2);
      Set1[val.second].erase(val2);
    }
    if (val.first == 0) {
      val1 = val;
      if (Set1[val1.second].size() != 1) continue;
      Set2[*Set1[val1.second].begin()].insert(val1.second);
      Set.erase(
          make_pair(p[*Set1[val1.second].begin()], *Set1[val1.second].begin()));
      p[*Set1[val1.second].begin()]++;
      Set.insert(
          make_pair(p[*Set1[val1.second].begin()], *Set1[val1.second].begin()));
      continue;
    }
    Set.insert(val);
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while (t--) solve();
  return 0;
}
