#include <bits/stdc++.h>
using namespace std;
vector<set<int>> leaves;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<set<int>> tree(n);
    leaves = vector<set<int>>(n);
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      x--, y--;
      tree[x].insert(y);
      tree[y].insert(x);
    }
    struct comp {
      bool operator()(const int lhs, const int rhs) const {
        if (leaves[lhs].size() == leaves[rhs].size()) return lhs < rhs;
        return leaves[lhs].size() > leaves[rhs].size();
      }
    };
    set<int, comp> nodeset;
    for (int i = 0; i < n; i++) {
      if (tree[i].size() == 1) leaves[*(tree[i].begin())].insert(i);
    }
    for (int i = 0; i < n; i++) nodeset.insert(i);
    int moves = 0;
    while (true) {
      int most = *(nodeset.begin());
      if (leaves[most].size() < k) break;
      for (int i = 0; i < k; i++) {
        int lv = *(leaves[most].begin());
        nodeset.erase(most);
        nodeset.erase(lv);
        leaves[most].erase(lv);
        leaves[lv].erase(most);
        tree[most].erase(lv);
        tree[lv].erase(most);
        if (tree[most].size() == 1) {
          int parent = *(tree[most].begin());
          nodeset.erase(parent);
          leaves[parent].insert(most);
          nodeset.insert(parent);
        }
        nodeset.insert(lv);
        nodeset.insert(most);
      }
      moves++;
    }
    cout << moves << endl;
  }
  return 0;
}
