#include<bits/stdc++.h>
using namespace std;
int TT,T,n,k,cnt,h[210000];
struct ll
{
	int to,nxt,bn;
}e[210000];
vector<int>g[210000];
void add(int u,int v,int bn)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].nxt=h[u];
	e[cnt].bn=bn;
	h[u]=cnt;
}
void work(int u,int fa,int w)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)continue;
		work(v,u,e[i].bn);
		g[w].push_back(e[i].bn);
		g[e[i].bn].push_back(w);
	}
}
int main()
{
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	cin>>TT>>T;
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1,u,v;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v,i);
			add(v,u,i);
		}
		for(int i=h[1];i;i=e[i].nxt)
		{
			int v=e[i].to;
			work(v,1,e[i].bn);
		}
		int w=0;
		for(int i=h[1];i;i=e[i].nxt)
		{
			if(i!=h[1])
			{
				g[e[i].bn].push_back(w);
				g[w].push_back(e[i].bn);
			}
			w=e[i].bn;
		}
		printf("%d\n",k*2);
	}
	return 0;
}
