/* Code by pp_orange */
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define pper(i,r,l) for(int i=r;i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lb(x) ((x)&-(x))
#define lg(x) (31^__builtin_clz(x))
const int mod = 998244353;
#define int ll
using namespace std;
inline int rd(){
	int x(0),f(1);char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void out(int X){
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) out(X/10);
	putchar(X%10+'0');
}
ll pw(ll x,int d){
	ll t = 1;
	for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;
	return t;
}
#define MAX 1005
const int B = 4;
const int D = MAX/B;
int dp[MAX][D+5];
int dp2[MAX][D+5];
int f[MAX][B+5];
int conv[MAX][D+5][2];
int tmpconv[D+5][2];
int rltconv[D+5][2];
int sz[MAX];
vector<int> v[MAX];
int n,k;
void dfs(int x,int fa){
	f[x][1] = 1;
	sz[x] = 1;
	for(auto to:v[x]){
		if(to==fa)continue;
		dfs(to,x);
		pper(i,sz[x],1){
			repp(j,1,sz[to]){
				f[x][i+j] = (f[x][i+j]+(ll)f[x][i]*f[to][j])%mod;
			}
			f[x][i] = ((ll)f[x][i]*f[to][0])%mod;
		}
		sz[x] += sz[to];
	}
	f[x][0] = (f[x][k]+f[x][k+1])%mod;
	repp(i,k+1,sz[x])f[x][i] = 0;
	// cout<<"x = "<<x<<endl;
	// repp(i,0,k){
	// 	cout<<f[x][i]<<' ';
	// }cout<<endl;
	return ;
}
void dfs2(int x,int fa){
	memset(conv[x],0,sizeof(conv[x]));
	conv[x][0][0] = 1;
	sz[x] = 1;
	int smlsz = 1;
	int lim = 1;
	int delim = 0;
	for(auto to:v[x]){
		if(to==fa)continue;
		dfs2(to,x);
		if(sz[to]<k){
			smlsz += sz[to];
			sz[x] += sz[to];
			// if(x==1){
			// 	cout<<"kjhsdfckajhsfdkjashdjka\n";
			// }
			continue;
		}
		memset(tmpconv,0,sizeof(tmpconv));
		int num = sz[to]/k;
		int res = sz[to]%k;
		smlsz += res;
		repp(i,0,min(res,num)){
			tmpconv[i][0] = dp[to][i];
		}
		if(num>res){
			repp(i,res,num-1){
				tmpconv[i][1] = (dp[to][i]-dp2[to][i]+mod)%mod;
			}
			delim = num-1;
		}else delim = num;

		// cout<<"xx = "<<x<<" -> "<<to<<endl;
		// cout<<num<<','<<res<<endl;
		
		
		memset(rltconv,0,sizeof(rltconv));
		repp(e1,0,1){
			repp(e2,0,1-e1){
				repp(i,0,lim){
					repp(j,0,delim){
						rltconv[i+j][e1+e2] = (rltconv[i+j][e1+e2]+(ll)conv[x][i][e1]*tmpconv[j][e2])%mod;
					}
				}
			}
		}
		memcpy(conv[x],rltconv,sizeof(rltconv));

		// if(x==3){
		// 	repp(i,0,1){
		// 		repp(j,0,lim){
		// 			cout<<tmpconv[j][i]<<',';
		// 		}cout<<endl;
		// 	}cout<<endl;
		// 	repp(i,0,1){
		// 		repp(j,0,lim){
		// 			cout<<conv[x][j][i]<<';';
		// 		}cout<<endl;
		// 	}cout<<endl;
		// }
		sz[x] += sz[to];
		lim += delim;
	}

	if(sz[x]<k){
		dp[x][0] = 1;
		return ;
	}
	int res = n%k;
	int num = n/k;

	repp(i,0,lim){
		if(smlsz-i<=k)dp[x][i] = (dp[x][i]+conv[x][i][0])%mod;
		else if(smlsz-i==k+1){
			dp2[x][i+1] = (dp2[x][i+1]+conv[x][i][0])%mod;
			dp[x][i+1] = (dp[x][i+1]+conv[x][i][0])%mod;
		}
	}
	repp(i,0,lim){
		if(smlsz+k-i<=k){
			dp[x][i] = (dp[x][i]+conv[x][i][1])%mod;
	//		assert(conv[x][i][1]==0);
		}else if(smlsz+k-i==k+1){
			dp2[x][i+1] = (dp2[x][i+1]+conv[x][i][1])%mod;
			dp[x][i+1] = (dp[x][i+1]+conv[x][i][1])%mod;
		}
	}

	// cout<<"X = "<<x<<endl;
	// // cout<<"smlsz = "<<smlsz<<endl;
	// repp(i,0,5){
	// 	cout<<dp[x][i]<<' ';
	// }cout<<endl<<endl;
	
	// repp(i,0,min(res,num)){
	// 	dp[x]
	// }
	// repp(i,res+1,num-1){

	// }
	return ;
}
signed main(){
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	int T = rd();
	while(T--){
		n = rd();
		k = rd();
		repp(i,1,n){
			v[i].clear();
		}
		rep(i,1,n){
			int x = rd();
			int y = rd();
			v[x].pb(y);
			v[y].pb(x);
		}
		if(k<=B){
			repp(i,1,n){
				repp(j,0,B){
					f[i][j] = 0;
				}
			}
			dfs(1,1);
			cout<<f[1][0]<<endl;
		}else{
			if(n%k>(n/k)){
				cout<<0<<endl;
				continue;
			}
			repp(i,1,n){
				rep(j,0,D+5){
					dp2[i][j] = dp[i][j] = 0;
				}
			}
			dfs2(1,1);
			cout<<dp[1][n%k]<<endl;
		}
	}
	return 0;
}