#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<set<int>> adj;
vector<set<int>> leaves;
bool cmp(int a, int b) {
  if ((int)leaves[a].size() == (int)leaves[b].size()) {
    return a < b;
  }
  return (int)leaves[a].size() > (int)leaves[b].size();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed;
  cout.precision(10);
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    adj = leaves = vector<set<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      adj[a].insert(b);
      adj[b].insert(a);
    }
    for (int i = 0; i < n; i++) {
      if (adj[i].size() == 1) {
        leaves[*adj[i].begin()].insert(i);
      }
    }
    set<int, decltype(cmp)*> s(cmp);
    for (int i = 0; i < n; i++) {
      s.insert(i);
    }
    int sol = 0;
    while (true) {
      int v = *s.begin();
      if (leaves[v].size() < k) {
        break;
      }
      for (int i = 0; i < k; i++) {
        int leaf = *leaves[v].begin();
        adj[leaf].erase(v);
        adj[v].erase(leaf);
        s.erase(v);
        s.erase(leaf);
        leaves[v].erase(leaf);
        if (leaves[leaf].count(v)) {
          leaves[leaf].erase(v);
        }
        if (adj[v].size() == 1) {
          int par = *adj[v].begin();
          s.erase(par);
          leaves[par].insert(v);
          s.insert(par);
        }
        s.insert(v);
        s.insert(leaf);
      }
      sol++;
    }
    cout << sol << "\n";
  }
  return 0;
}
