Little Cyan Fish has a tree $G = (V, E)$ with $n$ vertices. The vertices of the tree are numbered with positive integers from $1$ to $n$. The $i$-th ($1 \le i \le n - 1$) edge connects vertex $u_i$ and $v_i$.

Little Cyan Fish wants you to assign a positive integer $p_i$ from $1$ to $n$ to each vertex $i$, satisfying the following requirements:

• For each $1 \le i < j \le n$, $p_i \neq p_j$. In other words, $p_{1 \dots n}$ forms a permutation of length $n$.
• For each edge $(u, v) \in E$ on the tree, we have $p_u + p_v \le n + 1$.

Little Cyan Fish wants you to calculate how many permutations $p$ satisfy this condition. As usual, since this problem is Not a Work of Idol, Little Cyan Fish does not want you to output the answer modulo a large prime. Therefore, please output the answer modulo $4$.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains an integer $n$ ($1 \le n \le 10^6$), indicating the number of vertices in the tree.

The next $(n - 1)$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), indicating an edge connecting vertex $u_i$ and $v_i$. It is guaranteed that these $(n - 1)$ edges form a valid tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single line containing one integer, indicating the answer modulo $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