Little Cyan Fish hat einen Baum $G = (V, E)$ mit $n$ Knoten. Die Knoten des Baums sind mit positiven ganzen Zahlen von $1$ bis $n$ nummeriert. Die $i$-te ($1 \le i \le n - 1$) Kante verbindet die Knoten $u_i$ und $v_i$.

Little Cyan Fish möchte, dass du jedem Knoten $i$ eine positive ganze Zahl $p_i$ von $1$ bis $n$ zuweist, sodass die folgenden Anforderungen erfüllt sind:

• Für alle $1 \le i < j \le n$ gilt $p_i \neq p_j$. Mit anderen Worten: $p_{1 \dots n}$ bildet eine Permutation der Länge $n$.
• Für jede Kante $(u, v) \in E$ des Baums gilt $p_u + p_v \le n + 1$.

Little Cyan Fish möchte, dass du berechnest, wie viele Permutationen $p$ diese Bedingung erfüllen. Da diese Aufgabe wie üblich Not a Work of Idol heißt, möchte Little Cyan Fish nicht, dass du die Antwort modulo einer großen Primzahl ausgibst. Gib die Antwort daher bitte modulo $4$ aus.

Input

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe eine ganze Zahl $n$ ($1 \le n \le 10^6$), die die Anzahl der Knoten im Baum angibt.

Die nächsten $(n - 1)$ Zeilen enthalten jeweils zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), die eine Kante zwischen den Knoten $u_i$ und $v_i$ angeben. Es wird garantiert, dass diese $(n - 1)$ Kanten einen gültigen Baum bilden.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet.

Output

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die die Antwort modulo $4$ angibt.

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