Little Cyan Fish는 $n$개의 정점을 가진 트리 $G = (V, E)$를 가지고 있습니다. 트리의 정점은 $1$부터 $n$까지의 양의 정수로 번호가 매겨져 있습니다. $i$번째 ($1 \le i \le n - 1$) 간선은 정점 $u_i$와 $v_i$를 연결합니다.

Little Cyan Fish는 각 정점 $i$에 $1$부터 $n$까지의 양의 정수 $p_i$를 할당하여 다음 요구 사항을 만족시키고자 합니다:

• 모든 $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$가 몇 개인지 계산하고자 합니다. 평소와 같이, 이 문제는 Not a Work of Idol이 아니므로, Little Cyan Fish는 큰 소수로 나눈 나머지를 출력하기를 원하지 않습니다. 따라서, 답을 $4$로 나눈 나머지를 출력하십시오.

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 트리의 정점 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

다음 $(n - 1)$개의 줄에는 정점 $u_i$와 $v_i$를 연결하는 간선을 나타내는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq 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