桔梗精心培育了一棵树。现在这棵树已经枝繁叶茂，桔梗决定对它进行修剪。

这棵树目前有 $n$ 个顶点。桔梗计划删除一些顶点及其关联的边，使得剩余的部分仍然连通。显而易见，剩余的部分仍然是一棵树。

作为一只小胖猫，桔梗希望剩余的树是“一心一意”的，也就是说它只有一个重心（heart）。在这里，树的重心定义为一个顶点，当它被移除时，剩余连通分量的最大大小达到最小。如果有多个顶点满足这一条件，它们都被视为重心。

桔梗想知道有多少种这样剩余的非空树，使得其重心是唯一的。输出答案对 998244353 取模的结果。当且仅当两个剩余树的顶点集不同时，它们被认为是不同的。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示树中顶点的数量。

接下来的 $n - 1$ 行，每行包含两个正整数 $x, y$ ($1 \le x, y \le n, x \ne y$)，表示树 $T$ 中一条边的两个端点。

保证单个测试点中所有测试用例的 $n$ 之和不超过 $1.5 \times 10^4$。

输出格式

对于每个测试用例，输出一个整数，表示答案对 998244353 取模的结果。

样例

样例输入 1

3
5
1 2
1 3
3 4
3 5
6
1 2
1 3
1 4
2 5
2 6
6
1 2
2 3
2 4
3 5
4 6

样例输出 1

11
18
16

说明

对于第一个测试用例，单个剩余顶点必然是唯一的重心。两个剩余顶点必然形成两个重心。其他具有唯一重心的有效子集包括：$\{1, 2, 3\}$、$\{1, 3, 4\}$、$\{1, 3, 5\}$、$\{3, 4, 5\}$、$\{1, 3, 4, 5\}$ 和 $\{1, 2, 3, 4, 5\}$。有效子集的总数为 11。