Little Cyan Fish har et tre $G = (V, E)$ med $n$ noder. Nodene i treet er nummerert med positive heltall fra $1$ til $n$. Den $i$-te ($1 \le i \le n - 1$) kanten forbinder node $u_i$ og $v_i$.

Little Cyan Fish vil at du skal tildele et positivt heltall $p_i$ fra $1$ til $n$ til hver node $i$, slik at følgende krav er oppfylt:

• For hver $1 \le i < j \le n$ gjelder $p_i \neq p_j$. Med andre ord danner $p_{1 \dots n}$ en permutasjon av lengde $n$.
• For hver kant $(u, v) \in E$ i treet har vi $p_u + p_v \le n + 1$.

Little Cyan Fish vil at du skal beregne hvor mange permutasjoner $p$ som oppfyller denne betingelsen. Som vanlig, siden denne oppgaven heter Not a Work of Idol, ønsker ikke Little Cyan Fish at du skal skrive ut svaret modulo et stort primtall. Skriv derfor ut svaret modulo $4$.

Input

Det er flere testtilfeller. Den første linjen i inndataene inneholder ett enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen i inndataene et heltall $n$ ($1 \le n \le 10^6$), som angir antall noder i treet.

De neste $(n - 1)$ linjene inneholder hver to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som angir en kant som forbinder node $u_i$ og $v_i$. Det er garantert at disse $(n - 1)$ kantene danner et gyldig tre.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Output

For hvert testtilfelle, skriv ut én enkelt linje som inneholder ett heltall, som angir svaret 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