לדגיג הטורקיז הקטן יש עץ $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