#include <bits/stdc++.h>
using namespace std;
int main() {
  int t, zz = 1;
  cin >> t;
  while (t--) {
    int n, k, a, b, x;
    cin >> n >> k;
    vector<vector<int>> veze(n + 1);
    vector<int> cnt(n + 1);
    vector<int> leafs(n + 1);
    vector<int> bio(n + 1);
    for (int i = 0; i < n - 1; i++) {
      cin >> a >> b;
      veze[a].push_back(b);
      veze[b].push_back(a);
      cnt[a]++;
      cnt[b]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
      if (cnt[i] > 1) {
        continue;
      }
      bio[i] = 1;
      leafs[veze[i][0]]++;
    }
    for (int i = 1; i <= n; i++) {
      if (leafs[i] >= k) {
        q.push(i);
      }
    }
    int sol = 0;
    while (!q.empty()) {
      sol++;
      a = q.front();
      leafs[a] -= k;
      cnt[a] -= k;
      if (leafs[a] < k) {
        q.pop();
      }
      if (cnt[a] == 1) {
        bio[a] = 1;
        for (auto e : veze[a]) {
          if (bio[e] == 1) {
            continue;
          }
          leafs[e]++;
          if (leafs[e] == k) {
            q.push(e);
          }
        }
      }
    }
    if (k == 1) {
      cout << n - 1 << endl;
    } else {
      cout << sol << endl;
    }
    zz++;
  }
}
