Little Cyan Fish possède un arbre $G = (V, E)$ avec $n$ sommets. Les sommets de l'arbre sont numérotés avec des entiers positifs de $1$ à $n$. La $i$-ème arête ($1 \le i \le n - 1$) relie les sommets $u_i$ et $v_i$.

Little Cyan Fish souhaite que vous assigniez un entier positif $p_i$ compris entre $1$ et $n$ à chaque sommet $i$, en satisfaisant les conditions suivantes :

• Pour chaque $1 \le i < j \le n$, $p_i \neq p_j$. En d'autres termes, $p_{1 \dots n}$ forme une permutation de longueur $n$.
• Pour chaque arête $(u, v) \in E$ de l'arbre, nous avons $p_u + p_v \le n + 1$.

Little Cyan Fish veut que vous calculiez combien de permutations $p$ satisfont cette condition. Comme d'habitude, puisque ce problème n'est pas Not a Work of Idol, Little Cyan Fish ne veut pas que vous donniez la réponse modulo un grand nombre premier. Par conséquent, veuillez donner la réponse modulo $4$.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier unique $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$), indiquant le nombre de sommets dans l'arbre.

Les $(n - 1)$ lignes suivantes contiennent chacune deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), indiquant une arête reliant les sommets $u_i$ et $v_i$. Il est garanti que ces $(n - 1)$ arêtes forment un arbre valide.

Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $10^6$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier, indiquant la réponse modulo $4$.

Exemples

Entrée 1

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

Sortie 1

1
2
0
2