F. Shoo 打破阳光

每个测试的时间限制： $7$ 秒
内存限制： $256$ 兆字节

---

题目描述

你得到一棵有 $n$ 个顶点的树，其中每个顶点可以染成红色、蓝色或白色。一种染色的酷值定义为任意一个红色顶点与任意一个蓝色顶点之间的最大距离$^*$。

形式化地说，设第 $i$ 个顶点的颜色为 $c_i$，那么一种染色的酷值为： [ \max_{1 \le u, v \le n,\ c_u = \text{红},\ c_v = \text{蓝}} d(u,v) ] 其中 $d(u,v)$ 是 $u$ 和 $v$ 在树上的距离。如果没有红色顶点或没有蓝色顶点，则酷值为 $0$。

你的任务是计算所有 $3^n$ 种可能的染色方案中，酷值之和，结果对 $998244353$ 取模。

---

$^*$ 距离：树中两个顶点 $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$ 种染色方案中酷值之和，结果对 $998244353$ 取模。

---

示例

输入：

3
3
1 2
2 3
6
1 2
1 3
1 4
3 5
5 6
17
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
3 10
7 11
7 12
11 13
13 14
14 15
10 16
16 17

输出：

18
1920
78555509

---

样例解释

第一个测试用例：
共有 $12$ 种染色方案同时包含至少一个红色顶点和一个蓝色顶点。下图展示了这些染色方案及其酷值：

• 所有这些染色方案的酷值为 $2$（这里省略图示）
• 所有这些染色方案的酷值为 $1$（这里省略图示）

因此，所有染色方案的酷值之和为 $6 \cdot 2 + 6 \cdot 1 = 18$。

第二个测试用例：
其中一些染色方案的酷值为 $3$（例如……），等等。