题目描述

给定一个有 $n$ 个顶点和 $n-1$ 条边的无向连通图，其中 $n$ 被保证为奇数。你需要将所有 $n-1$ 条边分成 $\frac{n-1}{2}$ 组，满足以下条件：

• 每组恰好有 $2$ 条边
• 同一组中的 $2$ 条边共享一个顶点

计算在模 $998244353$ 下的有效分组方案数。如果有两个方案中有两条边在一个方案中属于同一组，在另一个方案中不属于同一组，则认为这两个方案是不同的。

输入格式

第一行一个整数 $T (1 \leq T \leq 100)$，表示数据组数 对于每组数据，

第一行包含一个整数 $n ( 3 \le n \le 10^4 )$，表示顶点的数量。
接下来的 $n-1$ 行，每行包含两个整数 $u, v( 1 \le u < v \le n )$，表示顶点 $u$ 与 $v$ 通过一条边相连。
保证 $n$ 为奇数，并且给定的图是连通的。

输出格式

输出一行包含一个整数，表示在模 $998244353$ 下的有效分组方案数。

样例

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

3
1

样例1边的划分如下：
$(1,2)和(1,3)一组,(1,7)和(4,7)一组,(5,7)和(6,7)一组$
$(1,2)和(1,3)一组,(1,7)和(5,7)一组,(4,7)和(6,7)一组$
$(1,2)和(1,3)一组,(1,7)和(6,7)一组,(4,7)和(5,7)一组$
一共三种