#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k, x, y, res = 0;
    cin >> n >> k;
    vector<vector<int>> gr(n + 1);
    vector<int> deg(n + 1, 0), ch(n + 1, 0), nxt;
    for (int i = 0; i < n - 1; i++) {
      cin >> x >> y;
      gr[x].push_back(y);
      gr[y].push_back(x);
      deg[x]++;
      deg[y]++;
    }
    for (int i = 1; i <= n; i++) {
      if (deg[i] == 1) {
        int par = gr[i].front();
        ch[par]++;
        if (ch[par] >= k) {
          nxt.push_back(par);
        }
      }
    }
    while (!nxt.empty()) {
      int a = nxt.back();
      nxt.pop_back();
      if (ch[a] < k) {
        continue;
      }
      vector<int> del;
      for (int i = 0; i < gr[a].size(); i++) {
        if (deg[gr[a][i]] == 1) {
          del.push_back(i);
        }
      }
      res += del.size() / k;
      while (del.size() % k != 0) {
        del.pop_back();
      }
      ch[a] -= del.size();
      for (int i = del.size() - 1; i >= 0; i--) {
        gr[a].erase(gr[a].begin() + del[i]);
      }
      deg[a] -= del.size();
      if (deg[a] == 1) {
        int par = gr[a].front();
        ch[par]++;
        if (ch[par] >= k) {
          nxt.push_back(par);
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}
