#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int sum,slv,k;//sum为son个数,slv为lv个数,k判断这个点有没有被当做叶子节点
	set<int> son,lv;//son连接的节点,lv连接的叶子节点
}a[200010];
signed main(){
	int T;
	cin >>T;
	while(T--){
		int n,k,ans=0;
		cin >>n>>k;
		for(int i=1;i<n;i++){
			int x,y;
			cin >>x>>y;
			a[x].sum++,a[y].sum++,a[x].son.insert(y),a[y].son.insert(x);//加边
		}
		for(int i=1;i<=n;i++){
			if(a[i].sum==1){
				a[i].k=1;
				for(auto it:a[i].son) a[it].slv++,a[it].lv.insert(i);//统计叶子节点
			}
		}
		bool flag=1;
		while(flag){
			flag=0;
			for(int i=1;i<=n;i++){
				while(a[i].slv>=k){//删边
					a[i].slv-=k,a[i].sum-=k,ans++;
					int cnt=0;
					vector<int> v;
					for(auto it:a[i].lv){
						if(cnt>=k) break;
						v.push_back(it);
						cnt++;
					}
					for(auto it:v){
						a[i].lv.erase(it),a[i].son.erase(it);
						a[it].son.clear(),a[it].lv.clear(),a[it].sum=a[it].slv=0;
					}
					flag=1;//若更新了节点，则继续循环
				}
				if(a[i].sum==1&&a[i].k!=1){
					a[i].k=1;//更新叶子节点
					for(auto it:a[i].son) a[it].slv++,a[it].lv.insert(i);
				}
			}
		}
		cout <<ans<<endl;
		for(int i=0;i<=n;i++) a[i].sum=0,a[i].slv=0,a[i].k=0,a[i].son.clear(),a[i].lv.clear();//清空
	}
	return 0;
}