树的重排
题号：NC318399
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Froggy 有一棵 n 个点的无根树 T，点带点权，初始点 i 的点权为 i。
Froggy 可以依次进行不超过 1 次以下操作：
1. 选择若干个两两不同的点 x_1,x_2,\cdots,x_k，满足对于 i=1,2,\cdots,k-1，树 T 上存在边连接点 x_i 和点 x_{i+1}。
2. 在 \{x_1,x_2,\cdots,x_k\} 中选择偶数个点 u_1,u_2,\cdots,u_{2l}（可以重复选择），对于 i=1,2,\cdots,l，依次交换点 u_{2i-1} 和点 u_{2i} 的点权。
记录 a_i 为所有操作结束后点 i 的点权，求 Froggy 可以得到多少个不同的序列 a_1,a_2,\cdots,a_n，答案对 998244353 取模。

输入描述:

第一行一个正整数 T (1\leq T\leq 10^3)，表示数据组数。
对于每组数据，第一行一个整数 n (1\leq n\leq 3000) 表示树的点数。
接下来 n-1 行，每行两个正整数 x,y (1\leq x,y\leq n,x\neq y)，表示树 T 上一条边的两个端点。
保证单个测试点内每组数据中 n 的和不超过 1.5\times 10^4。

输出描述:

对于每组数据，一行一个整数表示答案对 998244353 取模后的结果。
示例1

输入

复制 
3
5
1 2
1 3
1 4
1 5
6
1 2
1 3
1 4
2 5
2 6
6
1 2
2 3
2 4
3 5
4 6

输出

复制 
23
80
155