#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
#define int ll
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=998244353,M=5e7+10;
const char en='\n';
const ll LLINF=1ll<<60;

int t,n,k,ss[N],par[N];
ll sussI[N],sussO[N];
ll st[M];
vi ch[N],ch1[N];

void dfs(int i,int p=0)
{
	ss[i]=1;
	sussI[i]=0;
	par[i]=p;
	for (auto x: ch[i]) if (x!=p)
	{
		dfs(x,i);
		ch1[i].pb(x);
		ss[i]+=ss[x];
		sussI[i]+=sussI[x];
	}
	sussI[i]+=ss[i];
}

void dfs2(int i)
{
	ll su=sussO[i];
	for (auto x: ch1[i]) su+=sussI[x];
	for (auto x: ch1[i])
	{
		sussO[x]=su-sussI[x]+(n-ss[x]);
		dfs2(x);
	}
}

int mul(int a,int b)
{
	return a*1ll*b%MOD;
}

int sq(int a)
{
	return mul(a,a);
}

int cb(int a)
{
	return mul(a,sq(a));
}

void ad(int&a,int b)
{
	a+=b;
	if (a>=MOD) a-=MOD;
}

int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>k;
		for (int i=1;i<=n;++i) ch[i].clear(),ch1[i].clear();
		for (int i=1;i<n;++i)
		{
			int a,b;
			cin>>a>>b;
			ch[a].pb(b);
			ch[b].pb(a);
		}
		if (n==2)
		{
			int an=0;
			for (int i=1;i<=k;++i) ad(an,cb(sq(i)));
			cout<<an<<en;
			continue;
		}
		k-=n-1;
		int ro=1;
		while (ch[ro].size()==1) ++ro;
		sussO[ro]=0;
		dfs(ro);
		dfs2(ro);
		ll po=0;
		for (int i=2;i<=n;++i)
		{
			po+=ss[i]*1ll*sussO[i]+(n-ss[i])*1ll*sussI[i]-ss[i]*1ll*(n-ss[i]);
			po%=MOD;
		}
		vl vals;
		for (int i=1;i<=n;++i) if (ch[i].size()==1) vals.pb(2*sussO[i]+n-2+1);
		sort(all(vals));
		queue<ll> q;
		po%=MOD;
		int pt=1,an=cb(po),vs=vals.size();
		q.push(vals[0]);
		//cout<<po<<en;
		for (int i=0;i<k;++i)
		{
			ll u=q.front();
			q.pop();
			po=(po+u+2*i)%MOD;
			//cout<<po<<en;
			ad(an,cb(po));
			ll nov=u+2*(n-2);
			while (pt<vs && vals[pt]<nov) q.push(vals[pt]),++pt;
			q.push(nov);
		}
		cout<<an<<en;
	}
}