#include <bits/stdc++.h>

const int B = 350;
const int mod = 998244353;
using i64 = long long;

int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
 
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
struct mint {
    int x;
    mint(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    mint operator-() const {
        return mint(norm(mod - x));
    }
    mint inv() const {
        assert(x != 0);
        return power(*this, mod - 2);
    }
    mint &operator*=(const mint &rhs) {
        x = i64(x) * rhs.x % mod;
        return *this;
    }
    mint &operator+=(const mint &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    mint &operator/=(const mint &rhs) {
        return *this *= rhs.inv();
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res *= rhs;
        return res;
    }
    friend mint operator+(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res += rhs;
        return res;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res -= rhs;
        return res;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
        mint res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, mint &a) {
        i64 v;
        is >> v;
        a = mint(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint &a) {
        return os << a.val();
    }
};

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector adj(n + 1, std::vector<int>());
    std::vector dp(n + 1, std::vector<mint>(B));
    std::vector<int> sz(n + 1);
    for (int i = 1; i < n; i += 1){
        int u, v;
        std::cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    std::function<void(int, int) > dfs1 = [&](int u, int fa) {
        sz[u] = 1;
        dp[u][1] = 1;
        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs1(v, u);
            std::vector<mint> tmp(B);
            for (int i = std::min(k + 1, sz[u]); i >= 0; i -= 1){
                for (int j = std::min(sz[v], k + 1 - i); j >= 0; j -= 1) {
                    tmp[i + j] += dp[u][i] * dp[v][j];
                }
            }
            std::swap(tmp, dp[u]);
            sz[u] += sz[v];
        }
        dp[u][0] += dp[u][k + 1] + dp[u][k];
        dp[u][k + 1] = 0;
    };

    auto ceil = [](int x, int y) {
        return (x + y - 1) / y;
    };
    
    
    std::function<void(int, int) > dfs2 = [&](int u, int fa) {
        sz[u] = 1;
        dp[u][0] = 1;
        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs2(v, u);
            std::vector<mint> tmp(B);
            for (int i = ceil(sz[u], k); i >= 0; i -= 1){
                int x = sz[u] - i * k;
                if (dp[u][i].val() == 0 || x < 0) continue;
                for (int j = ceil(sz[v], k); j >= 0; j -= 1) {
                    int y = sz[v] - j * k;
                    if (y < 0) continue;
                    if (y % (k + 1) == k) {
                        tmp[i + j + 1] += dp[u][i] * dp[v][j];
                        if (y % (k + 1) + x % (k + 1) <= k + 1) {
                            tmp[i + j] += dp[u][i] * dp[v][j];
                        }
                        continue;
                    }
                    if(y % (k + 1) == 0) {
                        tmp[i + j] += dp[u][i] * dp[v][j];
                    }
                    else if (y % (k + 1) + x % (k + 1) <= k + 1) {
                        tmp[i + j] += dp[u][i] * dp[v][j];
                    }
                }
            }
            std::swap(tmp, dp[u]);
            sz[u] += sz[v];
        }
        // for (int i = 0; i <= ceil(sz[u], k); i += 1) {
        //     std::cerr << "dp[" << u << "][" << i << "] = " << dp[u][i] << "\n";
        // }
    };

    if (k <= B) {
        dfs1(1, 0);
        std::cout << dp[1][0] << "\n";
    }

    else {
        dfs2(1, 0);
        mint res = 0;
        for (int i = 0; i <= ceil(sz[1], k); i += 1) {
            int x = sz[1] - i * k;
            if (x < 0) continue;
            if (x % (k + 1) == 0 || x % (k + 1) == k) {
                res += dp[1][i];
            }
        }
        std::cout << res << "\n";
    }
}

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