#include <bits/stdc++.h>
const long double eps = 1e-9;
const long double pi = acos(-1.0);
using namespace std;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<set<int>> g(n + 1);
  vector<set<int>> leaves(n + 1);
  vector<int> cnt(n + 1, 0);
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].insert(y);
    g[y].insert(x);
  }
  for (int i = 1; i <= n; i++) {
    if (g[i].size() == 1) leaves[*g[i].begin()].insert(i);
  }
  set<pair<int, int>> st;
  for (int i = 1; i <= n; i++) st.insert({(int)leaves[i].size(), i});
  int ans = 0;
  while (st.size() != 0) {
    auto x = *st.rbegin();
    if (x.first < k) break;
    st.erase(x);
    for (int i = 0; i < k; i++) {
      int v = *leaves[x.second].begin();
      g[v].erase(x.second);
      g[x.second].erase(v);
      leaves[x.second].erase(v);
    }
    st.insert({leaves[x.second].size(), x.second});
    ans++;
    if (g[x.second].size() == 1) {
      st.erase({leaves[*g[x.second].begin()].size(), *g[x.second].begin()});
      leaves[*g[x.second].begin()].insert(x.second);
      st.insert({leaves[*g[x.second].begin()].size(), *g[x.second].begin()});
    }
  }
  if (k == 1) ans--;
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(10);
  int step;
  step = 1;
  cin >> step;
  for (int i = 1; i <= step; i++) {
    solve();
  }
}
