#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 414514
using namespace std;
int n,ans,T,k;
bool lf[N];
int g[N],son[N];
int head[N],to[N],nxt[N],f[N],tot; 
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void dfs(int x,int fa){
	bool flg=1;
//	printf("\n%d:\n",x);
//	for(int i=head[x];i;i=nxt[i]){
//		int y=to[i];
//		printf("%d ",y);
//	}
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
	//printf("%d ",y);
		if(y==fa)continue;
		dfs(y,x);
		if(lf[y])g[x]++;
		son[x]++;
		//printf("test:%d %d %d %d\n",y,x,g[x],son[x]);
		flg=0;
	}
	lf[x]=flg;
}
bool work(){
	bool flg=0;
//	puts("WORK");
	for(int x=1;x<=n;x++){
		if(g[x]>=k){
			flg=1;
			ans++;
			g[x]-=k;
			son[x]-=k;
			//printf("test:%d %d %d\n",x,g[x],son[x]);
			if(son[x]<=1){
				//printf("\n%d:\n",x);
				lf[x]=1;
				for(int i=head[x];i;i=nxt[i]){
					int y=to[i];
					if(lf[y])continue;
					//printf("%d ",y);
					g[y]++;
					//son[y]++;
				}
			}
		}
	}
	//puts("\nEND-WORK");
	return flg;
}
void solve(){while(work());}
signed main(){
	scanf("%d",&T);
	while(T--){
		tot=0;ans=0;
		scanf("%d%d",&n,&k);
		if(k==1){printf("%d\n",n-1);continue;}
		for(int i=1;i<n;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b);
			add(b,a);
		}
		dfs(1,0);
		solve();
		printf("%d\n",ans);
		memset(head,0,sizeof(head));
		memset(lf,0,sizeof(lf));
		memset(g,0,sizeof(g));
		memset(f,0,sizeof(f));
		memset(son,0,sizeof(son));
	}
	return 0;
}