لدى السمكة السماوية الصغيرة شجرة $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