Little Cyan Fish har ett träd $G = (V, E)$ med $n$ hörn. Trädets hörn är numrerade med positiva heltal från $1$ till $n$. Den $i$:te ($1 \le i \le n - 1$) kanten förbinder hörn $u_i$ och $v_i$.

Little Cyan Fish vill att du tilldelar ett positivt heltal $p_i$ från $1$ till $n$ till varje hörn $i$, så att följande krav är uppfyllda:

• För varje $1 \le i < j \le n$ gäller $p_i \neq p_j$. Med andra ord bildar $p_{1 \dots n}$ en permutation av längd $n$.
• För varje kant $(u, v) \in E$ i trädet gäller $p_u + p_v \le n + 1$.

Little Cyan Fish vill att du beräknar hur många permutationer $p$ som uppfyller detta villkor. Som vanligt, eftersom detta problem heter Not a Work of Idol, vill Little Cyan Fish inte att du skriver ut svaret modulo ett stort primtal. Skriv därför ut svaret modulo $4$.

Input

Det finns flera testfall. Den första raden i indata innehåller ett enskilt heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata ett heltal $n$ ($1 \le n \le 10^6$), som anger antalet hörn i trädet.

De följande $(n - 1)$ raderna innehåller var och en två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), som anger en kant som förbinder hörn $u_i$ och $v_i$. Det garanteras att dessa $(n - 1)$ kanter bildar ett giltigt träd.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Output

För varje testfall, skriv ut en enskild rad som innehåller ett heltal, vilket anger 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