偶像团体 Oshikoshi 请求你协助为他们的新专辑封面设计数学艺术。

专辑封面将是一棵树——它将展示 $n$ 个偶像，并有 $n - 1$ 条曲线，每条曲线双向连接一对不同的偶像。简单路径是指由两个或多个不同偶像组成的序列，使得序列中任意两个相邻偶像之间都有一条曲线直接相连；由于这是一棵树，任意两个偶像 $u$ 和 $v$ 之间都存在一条路径，且可以证明该路径是唯一的。因此，你可以验证任何具有 $n$ 个偶像的树都有 $n(n-1)/2$ 条不同的简单路径（如果我们认为从 $u$ 到 $v$ 的路径与从 $v$ 到 $u$ 的路径是“相同”的）。

Oshikoshi 给出了更多定义：

• 每条曲线的长度都是某个正整数。
• 整棵树的“墨水成本”等于其所有 $n - 1$ 条曲线的长度之和。
• 简单路径的长度等于该路径上所有曲线的长度之和。
• 路径的平方长度是指将路径长度取平方后得到的值。
  • 注意，是对路径上所有曲线的长度之和进行平方，而不是对单个长度进行平方（例如，在一条由长度为 3 和 4 的曲线组成的路径中，我们想要的是 $(3+4)^2$ 而不是 $3^2 + 4^2$）。
• 树的“戏剧性”等于树中所有 $n(n - 1)/2$ 条不同简单路径的平方长度之和。

现在，树的“形状”已经确定（即哪些偶像由 $n - 1$ 条曲线连接），但每条曲线的长度尚未确定。

你最初的任务是：给定一个整数 $c$，考虑所有为树中每条曲线分配正整数长度的方法，使得墨水成本恰好等于 $c$。在所有这些方法中，找到一种使树的戏剧性最小化的方法；设该最小戏剧性值为 $m(c)$。

但 Oshikoshi 想刁难你，所以他们改为问你以下问题：给定一个整数 $C$，求所有从 $n - 1$ 到 $C$（含）的整数 $c$ 的 $(m(c))^3$ 之和。请将此结果对 $998244353$ 取模。

输入格式

输入的第一行包含 $t$，即测试用例的数量。接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含两个空格分隔的整数 $n$ 和 $C$。接下来有 $n - 1$ 行，每行包含两个 $1$ 到 $n$ 之间的空格分隔整数，表示一对由曲线直接连接的偶像。偶像编号为 $1$ 到 $n$。

• $1 \le t \le 4$
• $2 \le n \le 3 \cdot 10^5$
• $n - 1 \le C \le 5 \cdot 10^7$

输出格式

对于每个测试用例，输出一行，包含一个整数，表示该测试用例的答案。

样例

样例输入 1

2
4 3
1 4
1 3
2 1
4 4
1 4
1 3
2 1

样例输出 1

3375
25327

说明

两个样例测试用例具有相同的树结构。

• 对于 $c = 3$，只有一种方法为所有 3 条曲线分配正整数长度，使得墨水成本恰好为 3，即为每条曲线分配 1。
  • 此时戏剧性为 $m(3) = 1^2 + 1^2 + 1^2 + 2^2 + 2^2 + 2^2 = 15$。
• 对于 $c = 4$，实现最小戏剧性的一种方法是为连接偶像 1 和 3 的曲线分配长度 2，并为其余两条曲线分配长度 1。
  • 此时戏剧性为 $m(4) = 1^2 + 2^2 + 1^2 + 3^2 + 2^2 + 3^2 = 28$。

因此， 第一个样例的答案是 $15^3 \pmod{998244353} = 3375$； 第二个样例的答案是 $(15^3 + 28^3) \pmod{998244353} = 25327$。