Маленька Блакитна Рибка має дерево $G = (V, E)$ з $n$ вершинами. Вершини дерева пронумеровані додатними цілими числами від $1$ до $n$. $i$-те ($1 \le i \le n - 1$) ребро з'єднує вершини $u_i$ та $v_i$.

Маленька Блакитна Рибка хоче, щоб ви поставили у відповідність кожній вершині $i$ додатне ціле число $p_i$ від $1$ до $n$, задовольняючи такі вимоги:

• Для кожних $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