#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 998244353;

constexpr int N = 1 << 19;

int que[N];

void solve() {
    int n, C;
    std::cin >> n >> C;

    C -= n - 1;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<std::array<i64, 3>> dp(n);
    auto dfs = [&](auto self, int x, int p = -1) -> void {
        dp[x][0] = 1;
        for (auto y : adj[x]) {
            if (y == p) {
                continue;
            }
            self(self, y, x);
            dp[x][0] += dp[y][0];
            dp[x][1] += dp[y][1] + dp[y][0];
            dp[x][2] = (dp[x][2] + dp[y][2] + 2 * dp[y][1] + dp[y][0]) % P;
        }
    };
    dfs(dfs, 0);

    auto dfs1 = [&](auto self, int x, int p = -1) -> void {
        for (auto y : adj[x]) {
            if (y == p) {
                continue;
            }
            i64 v0 = dp[x][0] - dp[y][0];
            i64 v1 = dp[x][1] - dp[y][1] - dp[y][0];
            i64 v2 = ((dp[x][2] - dp[y][2] - 2 * dp[y][1] - dp[y][0]) % P + P) % P;
            dp[y][0] += v0;
            dp[y][1] += v1 + v0;
            dp[y][2] = (dp[y][2] + v2 + 2 * v1 + v0) % P;
            self(self, y, x);
        }
    };
    dfs1(dfs1, 0);

    int res = 0;
    for (int x = 0; x < n; x++) {
        res = (res + dp[x][2]) % P;
    }
    res = 1LL * res * (P + 1) / 2 % P;
    std::vector<i64> a;
    for (int x = 0; x < n; x++) {
        if (adj[x].size() == 1) {
            a.push_back(2 * dp[x][1] + (n - 2));
        }
    }

    int ans = 0;
    std::sort(a.begin(), a.end());
    int i = 0;
    int l = 0, r = 0;
    for (int c = 0; c <= C; c++) {
        int v = (res + 1LL * c * c) % P;
        ans = (ans + 1LL * v * v % P * v) % P;
        i64 x;
        if (l != r && (i == a.size() || que[l] < a[i])) {
            x = que[l++];
            if (l == N) {
                l = 0;
            }
        } else {
            x = a[i++];
        }
        res = (res + x) % P;
        que[r++] = res + 2 * (n - 2);
        if (r == N) {
            r = 0;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}