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$ ($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