#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define N 300000
#define M 5000000
#define mod 998244353
using namespace std;
const int inv2=(mod+1)>>1;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
int T,n,sC,ans,tans,fa[N+1],C[3][3],l1,r1,l2,r2;
long long dp[N+1][3],delta[N+1],tong[N+1],dque[N+1],dque2[M+1];
bool used[N+1];
vector<int>E[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void adder(int x,int y,int d)
{
	for (int i=0;i<=2;++i)
		for (int j=0;j<=i;++j)
			dp[x][i]+=dp[y][j]*C[i][j]*d;
	return;
}
void dfs(int x)
{
	used[x]=dp[x][0]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			fa[E[x][i]]=x,dfs(E[x][i]),adder(x,E[x][i],1);
	return;
}
void dfs2(int x)
{
	Adder(ans,1ll*(dp[x][2]%mod)*inv2%mod);
	if (E[x].size()==1) delta[x]=2*dp[x][1];
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x)
			adder(x,E[x][i],-1),adder(E[x][i],x,1),dfs2(E[x][i]),adder(E[x][i],x,-1),adder(x,E[x][i],1);
	return;
}
int main()
{
	//freopen("idola.in","r",stdin);
	//freopen("idola.out","w",stdout);
	int x,y,rst;
	for (int i=0;i<=2;++i) C[i][0]=1;
	for (int i=1;i<=2;++i)
		for (int j=1;j<=i;++j)
			C[i][j]=C[i-1][j-1]+C[i-1][j];
	T=read();
	while (T--)
	{
		n=read(),sC=read()-(n-1),ans=tans=0;
		for (int i=1;i<=n;++i)
		{
			E[i].clear(),used[i]=fa[i]=0;
			for (int j=0;j<=2;++j) dp[i][j]=0;
		}
		for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
		if (n==2)
		{
			Adder(ans,1);
			for (int i=0;i<=sC;++i)
			{
				if (i) Adder(ans,1);
				Adder(tans,1ll*ans*ans%mod*ans%mod);
			}
			printf("%d\n",tans);
		}
		else
		{
			dfs(1),dfs2(1),l1=l2=1,r1=r2=0;
			for (int i=1;i<=n;++i)
				if (E[i].size()==1)
					dque[++r1]=delta[i]+n-2;
			sort(dque+1,dque+r1+1);
			for (int i=0;i<=sC;++i)
			{
				if (i)
				{
					if (l1<=r1&&(l2==r2+1||dque[l1]<dque2[l2])) Adder(ans,dque[l1]%mod),dque2[++r2]=dque[l1]+((n-2)<<1);
					else Adder(ans,dque2[l2]),dque2[++r2]=dque[l1]+((n-2)<<1);
					if (r2>2000000)
					{
						for (int i=r2-l2+1;i>=1;--i) dque2[i]=dque2[i+l2-1];
						r2-=(l2-1),l2=1;
					}
				}
				rst=MD(ans+1ll*i*i%mod),Adder(tans,1ll*rst*rst%mod*rst%mod);
			}
			printf("%d\n",tans);
		}
	}
	return 0;
}