Little Cyan Fish posiada drzewo $G = (V, E)$ o $n$ wierzchołkach. Wierzchołki drzewa są ponumerowane liczbami całkowitymi od $1$ do $n$. $i$-ta krawędź ($1 \le i \le n - 1$) łączy wierzchołki $u_i$ oraz $v_i$.

Little Cyan Fish chce, abyś przypisał każdemu wierzchołkowi $i$ liczbę całkowitą dodatnią $p_i$ z zakresu od $1$ do $n$, spełniającą następujące wymagania:

• Dla każdego $1 \le i < j \le n$, $p_i \neq p_j$. Innymi słowy, $p_{1 \dots n}$ tworzy permutację długości $n$.
• Dla każdej krawędzi $(u, v) \in E$ w drzewie zachodzi $p_u + p_v \le n + 1$.

Little Cyan Fish chce, abyś obliczył, ile permutacji $p$ spełnia ten warunek. Jak zwykle, ponieważ to zadanie nie jest Not a Work of Idol, Little Cyan Fish nie oczekuje wyniku modulo duża liczba pierwsza. W związku z tym, proszę podać wynik modulo $4$.

Wejście

Dane zawierają wiele zestawów testowych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T$), określającą liczbę zestawów testowych.

Dla każdego zestawu testowego pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), określającą liczbę wierzchołków w drzewie.

Kolejne $(n - 1)$ linii zawiera po dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), określające krawędź łączącą wierzchołki $u_i$ oraz $v_i$. Gwarantuje się, że te $(n - 1)$ krawędzi tworzy poprawne drzewo.

Gwarantuje się, że suma $n$ we wszystkich zestawach testowych nie przekracza $10^6$.

Wyjście

Dla każdego zestawu testowego wypisz w pojedynczej linii jedną liczbę całkowitą, oznaczającą wynik modulo $4$.

Przykład

Wejście 1

4
1
2
1 2
4
3 1
2 1
2 4
4
4 3
3 1
2 3

Wyjście 1

1
2
0
2