Little Cyan Fish có một cây $G = (V, E)$ với $n$ đỉnh. Các đỉnh của cây được đánh số bằng các số nguyên dương từ $1$ đến $n$. Cạnh thứ $i$ ($1 \le i \le n - 1$) nối đỉnh $u_i$ và $v_i$.

Little Cyan Fish muốn bạn gán một số nguyên dương $p_i$ từ $1$ đến $n$ cho mỗi đỉnh $i$, thỏa mãn các yêu cầu sau:

• Với mỗi $1 \le i < j \le n$, $p_i \neq p_j$. Nói cách khác, $p_{1 \dots n}$ tạo thành một hoán vị có độ dài $n$.
• Với mỗi cạnh $(u, v) \in E$ trên cây, ta có $p_u + p_v \le n + 1$.

Little Cyan Fish muốn bạn tính xem có bao nhiêu hoán vị $p$ thỏa mãn điều kiện này. Như thường lệ, vì bài toán này không phải là Not a Work of Idol, Little Cyan Fish không muốn bạn xuất kết quả theo modulo một số nguyên tố lớn. Do đó, hãy xuất kết quả theo modulo $4$.

Dữ liệu vào

Có nhiều bộ dữ liệu kiểm tra (test case). Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$), biểu thị số lượng đỉnh trong cây.

$(n - 1)$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), biểu thị một cạnh nối đỉnh $u_i$ và $v_i$. Đảm bảo rằng $(n - 1)$ cạnh này tạo thành một cây hợp lệ.

Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất ra một dòng duy nhất chứa một số nguyên, biểu thị kết quả theo modulo $4$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
2
0
2