#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 998244353;
const int maxn = 1e5 + 5;
const int B = 320;

int n, K, siz[maxn];
vector<int> G[maxn];
ll dp[maxn][B], g[B];

void dfs(int u, int fu)
{
	siz[u] = 1;
	for (int i = 0; i <= K + 1; i++) dp[u][i] = 0;
	dp[u][1] = 1;
	for (int v : G[u])
	{
		if (v == fu) continue;
		dfs(v, u);
		
		for (int j = 1; j <= min(K + 1, siz[u]); j++)
		{
            for (int k = 0; k <= min(K + 1 - j, siz[v]); k++)
                (g[j + k] += dp[v][k] * dp[u][j]) %= mod;
            (g[j] += dp[u][j] * dp[v][K]) %= mod;
            (g[j] += dp[u][j] * dp[v][K + 1]) %= mod;
		}
        
        siz[u] += siz[v];
        for (int j = 1; j <= min(K + 1, siz[u]); j++)
            dp[u][j] = g[j], g[j] = 0;
	}
}

void work1()
{
	dfs(1, 0);
	cout << (dp[1][K] + dp[1][K + 1]) % mod << "\n";
}

ll f[maxn][B], f2[maxn], fk[maxn][B], h[B];
void dfs2(int u, int fu)
{
	siz[u] = 1;
	f2[u] = 0;
	for (int i = 0; i <= n / K; i++) f[u][i] = fk[u][i] = 0;
	f[u][0] = 1;
	int sum = 0;
	for (int v : G[u])
	{
		if (v == fu) continue;
		dfs2(v, u);
		
		int x = siz[v] / K, y = siz[v] % K;
		sum += x;
		for (int j = siz[u] / K; ~j; j--)
		{
			if ((siz[u] - j) % K == 0 || (siz[u] - j) % K == 1)
			{
				for (int k = 0; k <= x; k++)
            	{
					if ((siz[v] - k) % K + (siz[u] - j) % K < K)
            			(g[j + k] += f[v][k] * f[u][j]) %= mod;
            		else if ((siz[v] - k) % K + (siz[u] - j) % K <= K + 1)
            			(h[j] += f[v][k] * f[u][j]) %= mod;
            		
					if ((siz[v] - k) % K + (siz[u] - j) % K <= 1)
						(h[j + k] += fk[u][j] * f[v][k]) %= mod;
				}
				
				(h[j + y] += f2[v] * f[u][j]) %= mod;
			}
			else
			{
				for (int k = 0; k <= x; k++)
				{
	            	if ((siz[u] - j) % K + (siz[v] - k) % K < K)
						(g[j + k] += f[v][k] * f[u][j]) %= mod;
					else if ((siz[u] - j) % K + (siz[v] - k) % K <= K + 1)
						(h[j + k] += f[v][k] * f[u][j]) %= mod;
				}
				if ((siz[u] - j) % K <= 1)
					(h[j + y] += f2[v] * f[u][j]) %= mod;
			}
		}
		
        siz[u] += siz[v];
        for (int j = 0; j <= siz[u] / K; j++)
        {
            f[u][j] = g[j], g[j] = 0;
            if ((siz[u] - j) % K > 1) fk[u][j] = 0;
            else fk[u][j] = h[j];
            h[j] = 0;
		}
	}
	
	for (int i = 0; i <= siz[u] / K; i++)
	{
		if ((siz[u] - i) % K == 0) (f[u][i] += fk[u][i]) %= mod;
		else if ((siz[u] - i) % K == 1) (f[u][i + 1] += fk[u][i]) %= mod;
		if ((siz[u] - i) % K == 0) f2[u] = fk[u][i];
	}
}

void work2()
{
	dfs2(1, 0);
	if ((n % K) * (K + 1) > n) cout << "0\n";
	else cout << f[1][n % K] << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--)
    {
    	cin >> n >> K;
    	for (int i = 1; i <= n; i++) G[i].clear();
    	for (int i = 1; i < n; i++)
    	{
    		int u, v;
    		cin >> u >> v;
    		G[u].emplace_back(v);
    		G[v].emplace_back(u);
		}
		
		int bs = (int)sqrt(n);
		if (K <= bs) work1();
		else work2();
	}
	return 0;
}