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

const int MOD = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> node(n + 1);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    int sq = 340;
    if (k <= sq) {
        vector<vector<ll>> dp(n + 1, vector<ll>(k + 2));
        vector<int> sz(n + 1);
        function<void(int, int)> dfs = [&](int x, int f) {
            dp[x][1] = 1;
            sz[x] = 1;
            for (auto e : node[x]) {
                if (e == f)
                    continue;
                vector<ll> ndp(k + 2);
                dfs(e, x);
                for (int i = 0; i <= min(k + 1, sz[e]); ++i) {
                    for (int j = 0; j <= min(k + 1, sz[x]); ++j) {
                        if (i + j > k + 1)
                            continue;
                        ndp[i + j] += dp[e][i] * dp[x][j] % MOD;
                    }
                }

                sz[x] += sz[e];
                for (int i = 0; i <= min(k + 1, sz[x]); ++i)
                    ndp[i] %= MOD;
                swap(dp[x], ndp);
            }
            dp[x][0] = (dp[x][k] + dp[x][k + 1]) % MOD;
            return;
        };
        dfs(1, 0);
        cout << dp[1][0] << '\n';
    }
    else {
        vector<vector<ll>> dp(n + 1, vector<ll>(n / k + 1));
        vector<int> sz(n + 1);
        function<void(int, int)> dfs = [&](int x, int f) {
            sz[x] = 1;
            dp[x][0] = 1;
            for (auto e : node[x]) {
                if (e == f)
                    continue;
                dfs(e, x);
                vector<ll> ndp(n / k + 1);
                for (int i = 0; i <= sz[e] / k; ++i) {
                    for (int j = 0; j <= sz[x] / k; ++j) {
                        int b = (sz[e] - i * k) % (k + 1);
                        int a = (sz[x] - j * k) % (k + 1);
                        if ((!a && !b) || (a && a + b <= k + 1))
                            (ndp[i + j] += dp[e][i] * dp[x][j]) %= MOD;
                    }
                }
                swap(dp[x], ndp);
                sz[x] += sz[e];
            }
            vector<ll> ndp(dp[x]);
            for (int i = 0; i <= sz[x] / k; ++i) {
                int a = (sz[x] - i * k) % (k + 1);
                if (a == k)
                    (ndp[i + 1] += dp[x][i]) %= MOD;
            }

            dp[x].swap(ndp);
            return;
        };
        dfs(1, 0);
        ll ans = 0;
        for (int i = 0; i <= n / k; ++i) {
            if ((n - i * k) % (k + 1) == 0)
                (ans += dp[1][i]) %= MOD;
        }
        cout << ans << '\n';
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}