ปลาเขียวตัวน้อยมีต้นไม้ $G = (V, E)$ ที่มีจุดยอด $n$ จุด จุดยอดของต้นไม้ถูกกำหนดหมายเลขด้วยจำนวนเต็มบวกตั้งแต่ $1$ ถึง $n$ เส้นเชื่อมเส้นที่ $i$ ($1 \le i \le n - 1$) เชื่อมจุดยอด $u_i$ และ $v_i$

ปลาเขียวตัวน้อยต้องการให้คุณกำหนดจำนวนเต็มบวก $p_i$ ตั้งแต่ $1$ ถึง $n$ ให้กับแต่ละจุดยอด $i$ โดยสอดคล้องกับเงื่อนไขต่อไปนี้:

• สำหรับแต่ละ $1 \le i < j \le n$ จะได้ $p_i \neq p_j$ กล่าวอีกนัยหนึ่ง $p_{1 \dots n}$ เป็นการเรียงสับเปลี่ยนที่มีความยาว $n$
• สำหรับแต่ละเส้นเชื่อม $(u, v) \in E$ บนต้นไม้ จะมี $p_u + p_v \le n + 1$

ปลาเขียวตัวน้อยต้องการให้คุณคำนวณว่ามีการเรียงสับเปลี่ยน $p$ กี่แบบที่สอดคล้องกับเงื่อนไขนี้ เช่นเคย เนื่องจากปัญหานี้คือ Not a Work of Idol ปลาเขียวตัวน้อยจึงไม่ต้องการให้คุณแสดงผลคำตอบมอดูโลจำนวนเฉพาะขนาดใหญ่ ดังนั้น โปรดแสดงผลคำตอบมอดูโล $4$

Input

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งตัว $T$ ($1 \le T$) แทนจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^6$) แทนจำนวนจุดยอดในต้นไม้

อีก $(n - 1)$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองตัว $u_i$ และ $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) แทนเส้นเชื่อมที่เชื่อมจุดยอด $u_i$ และ $v_i$ รับประกันว่าเส้นเชื่อม $(n - 1)$ เส้นนี้ประกอบกันเป็นต้นไม้ที่ถูกต้อง

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบไม่เกิน $10^6$

Output

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งตัว แทนคำตอบมอดูโล $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