#include <bits/stdc++.h>
using namespace std;
vector<int> adjList[200000];
int leafs[200000], rez, n, k;
void dfs(int cur) {
  while (leafs[cur] >= k) {
    int todo = k;
    ++rez;
    for (int ctr1 = adjList[cur].size() - 1; ctr1 >= 0; --ctr1) {
      if (adjList[adjList[cur][ctr1]].size() == 1) {
        adjList[adjList[cur][ctr1]].clear();
        --todo;
        --leafs[cur];
        swap(adjList[cur][ctr1], adjList[cur][adjList[cur].size() - 1]);
        adjList[cur].pop_back();
        if (todo == 0) break;
      }
    }
    if (adjList[cur].size() == 1) {
      ++leafs[adjList[cur].front()];
      if (leafs[adjList[cur].front()] >= k) dfs(adjList[cur].front());
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    vector<pair<int, int> > q;
    cin >> n >> k;
    for (int ctr1 = 0; ctr1 < n; ++ctr1) adjList[ctr1].clear(), leafs[ctr1] = 0;
    int a, b;
    for (int ctr1 = 1; ctr1 < n; ++ctr1)
      cin >> a >> b, --a, --b, adjList[a].push_back(b), adjList[b].push_back(a);
    for (int ctr1 = 0; ctr1 < n; ++ctr1)
      if (adjList[ctr1].size() == 1) ++leafs[adjList[ctr1].front()];
    rez = 0;
    if (k > 1) {
      for (int ctr1 = 0; ctr1 < n; ++ctr1) dfs(ctr1);
    } else {
      rez = n - 1;
    }
    cout << rez << '\n';
  }
  return 0;
}
