小青魚有一棵有 $n$ 個頂點嘅樹 $G = (V, E)$。樹嘅頂點用由 $1$ 到 $n$ 嘅正整數編號。第 $i$（$1 \le i \le n - 1$）條邊連接住頂點 $u_i$ 同 $v_i$。

小青魚想你為每個頂點 $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$。

小青魚想你計出有幾多個排列 $p$ 滿足呢個條件。同平時一樣，因為呢道題係非偶像之作，小青魚唔想你輸出對大質數取模嘅答案。因此，請輸出對 $4$ 取模之後嘅答案。

Input

輸入包含多組測試資料。輸入嘅第一行包含一個整數 $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$。

Output

對於每組測試資料，輸出一行包含一個整數，代表對 $4$ 取模之後嘅答案。

Examples

Input 1

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

Output 1

1
2
0
2