#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mid ((l+r)/2)
const int N=3e5+5,M=5e7+5,MOD=998244353,inv2=499122177;
int T,n,m,rt,d,nw,hd,tl,ans,sz[N];
ll t,a[N],s[N],s1[N],q[M];vector<int> e[N];
void dfs(int u,int f)
{sz[u]=1;s[u]=0;for(auto v:e[u]) if(v!=f) dfs(v,u),sz[u]+=sz[v],s[u]+=s[v]+sz[v];}
void dfs1(int u,int f)
{for(auto v:e[u]) if(v!=f) s1[v]=s1[u]+s[u]-s[v]-sz[v]+n-sz[v],dfs1(v,u);}
ll get()
{
	while(nw<=a[0] && a[nw]<q[hd]+d) q[++tl]=a[nw++];
	q[++tl]=q[hd]+d;return q[hd++];
}
void slv()
{
	scanf("%d %d",&n,&m);d=n*2-4;t=ans=a[0]=0;
	for(int i=1;i<=n;++i) e[i].clear();
	for(int i=1,u,v;i<n;++i) scanf("%d %d",&u,&v),e[u].pb(v),e[v].pb(u);
	if(n==2)
	{
		for(int i=1;i<=m;++i) ans=(ans+1ll*i*i%MOD*i)%MOD;
		printf("%d\n",ans);return;
	}for(int i=1;i<=n;++i) if(e[i].size()>1) rt=i;dfs(rt,0);dfs1(rt,0);
	for(int i=1;i<=n;++i) if(i!=rt) t=(t+s[i]*(n-sz[i])+s1[i]*sz[i])%MOD;
	for(int i=1;i<=n;++i) if(e[i].size()<2) a[++a[0]]=s1[i];
	sort(a+1,a+a[0]+1);for(int i=1;i<=a[0];++i) a[i]=a[i]*2+n-2;
	nw=2;hd=1;tl=0;q[++tl]=a[1];
	for(int i=0,t1;i<=m-n+1;++i)
		t1=(t+1ll*i*i)%MOD,ans=(ans+1ll*t1*t1%MOD*t1)%MOD,t+=get();
	printf("%d\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--) slv();return 0;
}