给你一棵有 $$$n$$$ 个顶点的树,其中每个顶点可以是红色、蓝色或白色。的 凉爽 被定义为红色和蓝色顶点之间的最大距离$$$^{\text{*}}$$$。
形式上,如果我们将第 $$$i$$$ 个顶点的颜色表示为 $$$c_i$$$,则在所有顶点对 $$$1\le u, v\le n$$$ 上,颜色的冷度为 $$$\max d(u, v)$$$,其中 $$$c_u$$$ 为 红色 和 $$$c_v$$$ 是 蓝色。如果没有红色或蓝色顶点,则冷度为零。
你的任务是计算树的所有 $$$3^n$$$ 可能颜色的酷度总和,以 $$$998\,244\,353$$$ 为模。
$$$^{\text{*}}$$$树中两个顶点$$$a$$$和$$$b$$$之间的距离等于顶点$$$a$$$和顶点$$$b$$$之间唯一简单路径上的边数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 3000$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行均包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u, v\le n$$$) - 树边缘的端点。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,输出树的所有 $$$3^n$$$ 可能颜色的酷度总和,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
331 22 361 21 31 43 55 6171 21 31 41 52 62 72 83 93 107 117 1211 1313 1414 1510 1616 17
输出复制
18 1920 78555509
注意
在第一个测试用例中,有 $$$12$$$ 颜色至少有一个蓝色和一个红色节点。下面的图片展示了它们的色彩和酷感:
所有这些颜色都很酷$$$2$$$
所有这些颜色都很酷$$$1$$$ 因此,所有可能颜色的酷度总和为 $$$6\cdot 2 + 6\cdot 1 = 18$$$。
在第二个测试用例中,以下是一些冷度为 $$$3$$$ 的着色示例: