#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct Edge
{
	int nxt;
	int to;
}
edge[800010];
int head[400010],size;
void add(int from,int to)
{
	edge[++size].nxt=head[from];
	edge[size].to=to;
	head[from]=size;
}
int n,k;
int u,v,root;
int s[400010];
int a[400010];
void init()
{
	size=0;
	memset(head,-1,sizeof(head));
	memset(edge,-1,sizeof(edge));
	memset(a,0,sizeof(a));
	memset(s,0,sizeof(s));
}
void work()
{
	init();
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
		s[u]++;
		s[v]++;
	}
	for(int i=1;i<=n;i++)
		if(s[i]==1)
			q.push(i),a[i]=1;
	queue<int> q;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(int i=head[u];~i;i=edge[i].nxt)
		{
			s[edge[i].to]--;
			if(s[edge[i].to]==1)
				a[edge[i].to]=a[u]+1,q.push(edge[i].to);
		}
	}
	int ans=n;
	for(int i=1;i<=n;i++)
		if(a[i]<=k)
			ans--;
	printf("%d\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
		work();
	return 0;
}