Little Cyan Fish ha un albero $G = (V, E)$ con $n$ vertici. I vertici dell'albero sono numerati con interi positivi da $1$ a $n$. L'$i$-esimo ($1 \le i \le n - 1$) arco collega i vertici $u_i$ e $v_i$.

Little Cyan Fish vuole che tu assegni a ciascun vertice $i$ un intero positivo $p_i$ da $1$ a $n$, soddisfacendo i seguenti requisiti:

• Per ogni $1 \le i < j \le n$, vale $p_i \neq p_j$. In altre parole, $p_{1 \dots n}$ forma una permutazione di lunghezza $n$.
• Per ogni arco $(u, v) \in E$ dell'albero, si ha $p_u + p_v \le n + 1$.

Little Cyan Fish vuole che tu calcoli quante permutazioni $p$ soddisfano questa condizione. Come al solito, poiché questo problema si intitola Not a Work of Idol, Little Cyan Fish non vuole che tu stampi la risposta modulo un numero primo grande. Pertanto, stampa la risposta modulo $4$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ciascun caso di test, la prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^6$), che indica il numero di vertici nell'albero.

Le successive $(n - 1)$ righe contengono ciascuna due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), che indicano un arco che collega i vertici $u_i$ e $v_i$. È garantito che questi $(n - 1)$ archi formino un albero valido.

È garantito che la somma di $n$ su tutti i casi di test non superi $10^6$.

Output

Per ciascun caso di test, stampa una singola riga contenente un intero, che indica la risposta 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