У Little Cyan Fish есть дерево $G = (V, E)$ с $n$ вершинами. Вершины дерева пронумерованы целыми числами от $1$ до $n$. $i$-е ($1 \le i \le n - 1$) ребро соединяет вершины $u_i$ и $v_i$.

Little Cyan Fish хочет, чтобы вы присвоили каждой вершине $i$ целое число $p_i$ от $1$ до $n$, удовлетворяющее следующим требованиям:

• Для любых $1 \le i < j \le n$, $p_i \neq p_j$. Иными словами, $p_1 \dots p_n$ образуют перестановку длины $n$.
• Для каждого ребра $(u, v) \in E$ дерева выполняется условие $p_u + p_v \le n + 1$.

Little Cyan Fish хочет, чтобы вы вычислили, сколько перестановок $p$ удовлетворяют этому условию. Как обычно, поскольку эта задача — не Work of Idol, Little Cyan Fish не хочет, чтобы вы выводили ответ по модулю большого простого числа. Поэтому выведите ответ по модулю $4$.

Входные данные

Входные данные содержат несколько тестовых случаев. Первая строка содержит единственное целое число $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$.

Выходные данные

Для каждого тестового случая выведите одну строку, содержащую одно целое число — ответ по модулю $4$.

Примеры

Входные данные 1

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

Выходные данные 1

1
2
0
2