Little Cyan Fish 有一棵包含 $n$ 个顶点的树 $G = (V, E)$。树的顶点编号为从 $1$ 到 $n$ 的正整数。第 $i$ 条边 ($1 \le i \le n - 1$) 连接顶点 $u_i$ 和 $v_i$。

Little Cyan Fish 希望你为每个顶点 $i$ 分配一个从 $1$ 到 $n$ 的正整数 $p_i$，并满足以下要求：

• 对于每个 $1 \le i < j \le n$，$p_i \neq p_j$。换句话说，$p_{1 \dots n}$ 构成一个长度为 $n$ 的排列。
• 对于树上的每条边 $(u, v) \in E$，满足 $p_u + p_v \le n + 1$。

Little Cyan Fish 想让你计算有多少种排列 $p$ 满足此条件。由于这个问题不是 Not a Work of Idol，Little Cyan Fish 不希望你输出对大质数取模的结果。因此，请输出答案对 $4$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示树的顶点数。

接下来的 $(n - 1)$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示连接顶点 $u_i$ 和 $v_i$ 的一条边。保证这 $(n - 1)$ 条边构成一棵合法的树。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案对 $4$ 取模的结果。

样例

输入 1

4
1
2
1 2
4
3 1
2 1
2 4
4
4 3
3 1
2 3

输出 1

1
2
0
2