Pikku syaanikalalla on puu $G = (V, E)$, jossa on $n$ solmua. Puun solmut on numeroitu positiivisilla kokonaisluvuilla luvusta $1$ lukuun $n$. $i$-s ($1 \le i \le n - 1$) kaari yhdistää solmut $u_i$ ja $v_i$.

Pikku syaanikala haluaa sinun asettavan jokaiselle solmulle $i$ positiivisen kokonaisluvun $p_i$ luvusta $1$ lukuun $n$ siten, että seuraavat vaatimukset täyttyvät:

• Jokaisella $1 \le i < j \le n$ pätee $p_i \neq p_j$. Toisin sanoen $p_{1 \dots n}$ muodostaa pituutta $n$ olevan permutaation.
• Jokaiselle puun kaarelle $(u, v) \in E$ pätee $p_u + p_v \le n + 1$.

Pikku syaanikala haluaa sinun laskevan, kuinka moni permutaatio $p$ täyttää tämän ehdon. Kuten tavallista, koska tämä tehtävä on Not a Work of Idol, Pikku syaanikala ei halua sinun tulostavan vastausta modulo suuri alkuluku. Tulosta siksi vastaus modulo $4$.

Input

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$), joka ilmaisee puun solmujen lukumäärän.

Seuraavat $(n - 1)$ riviä sisältävät kukin kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), jotka ilmaisevat solmut $u_i$ ja $v_i$ yhdistävän kaaren. On taattu, että nämä $(n - 1)$ kaarta muodostavat kelvollisen puun.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$.

Output

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää yhden kokonaisluvun: vastauksen 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