Litli blágræni fiskurinn á tré $G = (V, E)$ með $n$ hnútum. Hnútar trésins eru númeraðir með jákvæðum heiltölum frá $1$ til $n$. $i$-ti ($1 \le i \le n - 1$) leggurinn tengir saman hnúta $u_i$ og $v_i$.

Litli blágræni fiskurinn vill að þú úthlutir jákvæðri heiltölu $p_i$ frá $1$ til $n$ á hvern hnút $i$, þannig að eftirfarandi skilyrði séu uppfyllt:

• Fyrir hvert $1 \le i < j \le n$ gildir $p_i \neq p_j$. Með öðrum orðum myndar $p_{1 \dots n}$ umröðun af lengd $n$.
• Fyrir hvern legg $(u, v) \in E$ í trénu gildir $p_u + p_v \le n + 1$.

Litli blágræni fiskurinn vill að þú reiknir hversu margar umraðanir $p$ uppfylla þetta skilyrði. Eins og venjulega, þar sem þetta verkefni heitir Not a Work of Idol, vill Litli blágræni fiskurinn ekki að þú skrifir út svarið modulo stór frumtala. Vinsamlegast skrifaðu því út svarið modulo $4$.

Input

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu heiltölu $n$ ($1 \le n \le 10^6$), sem gefur til kynna fjölda hnúta í trénu.

Næstu $(n - 1)$ línur innihalda hver um sig tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), sem gefa til kynna legg sem tengir saman hnúta $u_i$ og $v_i$. Tryggt er að þessir $(n - 1)$ leggir myndi gilt tré.

Tryggt er að summan af $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Output

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem táknar svarið 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