#include <bits/stdc++.h>
using namespace std;
const int N = 1000010, mod = 1e9 + 7, INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n, k;
vector<set<int>> v, leaf;
struct cmp {
  bool operator()(int a, int b) const {
    if (leaf[a].size() == leaf[b].size()) return a < b;
    return leaf[a].size() > leaf[b].size();
  }
};
int solve() {
  if (k == 1) return n - 1;
  set<int, cmp> s;
  int ans = 0;
  for (int i = 0; i < n; i++) s.insert(i);
  while (1) {
    int now = *s.begin();
    if (leaf[now].size() < k) break;
    for (int i = 1; i <= k; i++) {
      int to = *leaf[now].begin();
      s.erase(now);
      s.erase(to);
      leaf[now].erase(to);
      v[now].erase(to);
      v[to].erase(now);
      if (leaf[to].count(now)) leaf[to].erase(now);
      if (v[now].size() == 1) {
        int ne = *v[now].begin();
        s.erase(ne);
        leaf[ne].insert(now);
        s.insert(ne);
      }
      s.insert(now);
      s.insert(to);
    }
    ans++;
  }
  return ans;
}
int main() {
  int _;
  scanf("%d", &_);
  while (_--) {
    scanf("%d%d", &n, &k);
    v = vector<set<int>>(n);
    leaf = vector<set<int>>(n);
    for (int i = 1; i <= n - 1; i++) {
      int a, b;
      scanf("%d%d", &a, &b);
      a--;
      b--;
      v[a].insert(b);
      v[b].insert(a);
    }
    for (int i = 0; i < n; i++)
      if (v[i].size() == 1) {
        leaf[*v[i].begin()].insert(i);
      }
    printf("%d\n", solve());
  }
  return 0;
}
