#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=sqrt(N)+10;
const int P=998244353;
int T,n,k,sz[N],f[N][M],F[N],A[M];
vector<int>e[N];
void solve1(int u,int fa)
{
	for(int i=0;i<=k+1;i++)
		f[u][i]=0;
	sz[u]=1;
	f[u][1]=1;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		solve1(v,u);
		for(int i=0;i<=k+1;i++)
			A[i]=0;
		for(int i=1;i<=min(sz[u],k+1);i++)
			for(int j=0;j<=min(sz[v],k);j++)
				A[i+j]=(A[i+j]+1ll*f[u][i]*f[v][j])%P;
		for(int i=1;i<=k+1;i++)
			f[u][i]=A[i];
		sz[u]+=sz[v];
	}
	f[u][0]=(f[u][k]+f[u][k+1])%P;
}
/*
合并进去时有一条边，切断/不切断 
合法必切断，不合法必不切断 
特殊情况：合法不切断：k的 
*/
void solve2(int u,int fa)
{
	sz[u]=1;
	int siz=0;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		solve2(v,u);
		sz[u]+=sz[v];
		siz+=sz[v]/k;
	}
	for(int i=0;i<=sz[u]/k;i++)
		f[u][i]=0;
	F[u]=0;
	if(siz<=sz[u]/k-2)return;
	int opt=0;
	if(siz==sz[u]/k)opt=1;
	sz[u]=1;
	f[u][0]=1;
	int tmp1=1,tmp2=0,tmp3=1;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		for(int i=0;i<=sz[v]/k+sz[u]/k;i++)
			A[i]=0;
		for(int i=0;i<=sz[u]/k;i++)
		{
			for(int j=0;j<=sz[v]/k;j++)
				A[i+j]=(A[i+j]+1ll*f[u][i]*f[v][j])%P;
			if(opt)
			{
				tmp3=1ll*tmp3*f[v][sz[v]%k]%P;
				tmp2=(1ll*tmp2*f[v][sz[v]%k]+1ll*tmp1*F[v])%P;
				tmp1=1ll*tmp1*F[v]%P;
			}
		}
		for(int j=0;j<=sz[v]/k+sz[u]/k;j++)
			f[u][j]=A[j];
		sz[u]+=sz[v];
	}
	if(opt)
	{
		F[u]=f[u][sz[u]%k];
		if(sz[u]%k)
		{
			f[u][sz[u]%k]=((f[u][sz[u]%k]+f[u][sz[u]%k-1]-tmp3)%P+P)%P;
			f[u][sz[u]%k-1]=tmp3;
		}
		f[u][sz[u]%k]=(f[u][sz[u]%k]+tmp2)%P;
		return;
	}
	for(int j=0;j<=sz[u]/k;j++)
		A[j]=f[u][j],f[u][j]=0;
	for(int j=0;j<=sz[u]/k;j++)
	{
		int tmp=sz[u]-(siz*k+j);
		if(tmp==k)f[u][j]=(f[u][j]+A[j])%P,F[u]=(F[u]+A[j])%P;
		if(tmp==k+1)f[u][j+1]=(f[u][j+1]+A[j])%P;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> T;
	while(T--)
	{
		cin >> n >> k;
		for(int i=1;i<=n;i++)
			e[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin >> u >> v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		if(1ll*k*k<=n)
		{
			solve1(1,0);
			cout << f[1][0] << endl;
		}
		else
		{
			solve2(1,0);
			if(sz[1]%k<=sz[1]/k)
				cout << f[1][sz[1]%k] << endl;
			else cout << "0\n";
		}
	}
	return 0;
}