Little Cyan Fish tiene un árbol $G = (V, E)$ con $n$ vértices. Los vértices del árbol están numerados con enteros positivos del $1$ al $n$. La $i$-ésima arista ($1 \le i \le n - 1$) conecta los vértices $u_i$ y $v_i$.

Little Cyan Fish quiere que asignes un entero positivo $p_i$ del $1$ al $n$ a cada vértice $i$, satisfaciendo los siguientes requisitos:

• Para cada $1 \le i < j \le n$, $p_i \neq p_j$. En otras palabras, $p_{1 \dots n}$ forma una permutación de longitud $n$.
• Para cada arista $(u, v) \in E$ en el árbol, tenemos $p_u + p_v \le n + 1$.

Little Cyan Fish quiere que calcules cuántas permutaciones $p$ satisfacen esta condición. Como de costumbre, dado que este problema no es Not a Work of Idol, Little Cyan Fish no quiere que des la respuesta módulo un número primo grande. Por lo tanto, por favor entrega la respuesta módulo $4$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^6$), que indica el número de vértices en el árbol.

Las siguientes $(n - 1)$ líneas contienen cada una dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), que indican una arista que conecta los vértices $u_i$ y $v_i$. Se garantiza que estas $(n - 1)$ aristas forman un árbol válido.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $10^6$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un entero, indicando la respuesta módulo $4$.

Ejemplos

Entrada 1

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

Salida 1

1
2
0
2