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 p_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$ を結ぶ辺を示す2つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) が含まれます。これらの $n - 1$ 本の辺は有効な木を形成することが保証されています。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されています。

出力

各テストケースについて、答えを $4$ で割った余りを1行で出力してください。

入出力例

入力 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