Given a binary tree with $4n - 1$ nodes, where each non-leaf node has exactly two children. The non-leaf nodes are numbered from $1$ to $2n - 1$, and the leaf nodes are numbered from $2n$ to $4n - 1$. Initially, no leaf node has a number.

A DFS order is defined as beautiful if and only if the sequence formed by the numbers on all leaf nodes that have been assigned a number, when traversed in that DFS order, can be reduced to an empty sequence by repeatedly removing adjacent identical numbers. For example, in the figure below, if leaf nodes $4$ and $6$ are labeled with $1$, and leaf nodes $5$ and $7$ are labeled with $2$, then the sequence formed by the numbers on the leaf nodes in the DFS order $[1, 4, 2, 7, 3, 5, 6]$ is $[1, 2, 2, 1]$. This can be reduced to $[1, 1]$ by removing the adjacent $2$s, and then to an empty sequence by removing the adjacent $1$s; thus, this DFS order is beautiful. However, for the DFS order $[1, 4, 2, 3, 5, 6, 7]$, the sequence is $[1, 2, 1, 2]$, which cannot be reduced to an empty sequence by repeatedly removing adjacent identical numbers; thus, this DFS order is not beautiful.

There are $n$ operations. In the $i$-th operation ($1 \le i \le n$), two leaf nodes that do not currently have a number are chosen, and these two nodes are labeled with the number $i$. It is guaranteed that after each operation, there exists at least one beautiful DFS order. You are required to find the number of beautiful DFS orders after each operation. Since the answer may be large, you only need to output the result modulo $1,000,000,007$.

Input

The first line contains a non-negative integer $c$, representing the test case number. $c = 0$ indicates that this test case is a sample. The second line contains a positive integer $n$, indicating that the binary tree has $4n - 1$ nodes. The $i+2$-th line ($1 \le i \le 2n - 1$) contains two positive integers $l_i$ and $r_i$, representing the left and right children of node $i$, respectively. It is guaranteed that $i < l_i, r_i \le 4n - 1$, and all $l_i, r_i$ are distinct. The $i+2n+1$-th line ($1 \le i \le n$) contains two positive integers $a_i, b_i$, representing the indices of the leaf nodes chosen in the $i$-th operation. It is guaranteed that $2n \le a_i, b_i \le 4n - 1$, and all $a_i, b_i$ are distinct.

Output

Output $n$ lines, where the $i$-th line contains a non-negative integer representing the number of beautiful DFS orders after the $i$-th operation, modulo $1,000,000,007$.

Examples

Input 1

0
2
4 2
3 7
5 6
4 6
5 7

Output 1

8
4

Note 1

This sample is the example shown in the problem description. After the first operation, leaf nodes $4$ and $6$ are labeled with $1$, and leaf nodes $5$ and $7$ have no numbers. Thus, the sequence formed by any DFS order is $[1, 1]$, meaning all $2^3 = 8$ DFS orders are beautiful. After the second operation, leaf nodes $4 \sim 7$ are labeled with $1, 2, 1, 2$ respectively. There are $4$ beautiful DFS orders: $[1, 4, 2, 3, 6, 5, 7]$, $[1, 4, 2, 7, 3, 5, 6]$, $[1, 2, 3, 6, 5, 7, 4]$, and $[1, 2, 7, 3, 5, 6, 4]$.

Input 2

0
6
2 3
4 21
22 23
5 11
6 8
7 9
12 13
10 18
14 15
16 17
19 20
12 13
14 15
16 19
17 18
20 21
22 23

Output 2

2048
2048
2048
1024
512
512

Constraints

For all test data, it is guaranteed that: $1 \le n \le 2 \times 10^5$; For all $1 \le i \le 2n - 1$, $i < l_i, r_i \le 4n - 1$, and all $l_i, r_i$ are distinct; For all $1 \le i \le n$, $2n \le a_i, b_i \le 4n - 1$, and all $a_i, b_i$ are distinct; After each operation, there exists at least one beautiful DFS order.

Special Property A: It is guaranteed that the two leaf nodes chosen in each operation are located in different subtrees of node $1$. Special Property B: It is guaranteed that there exists a non-negative integer $m$ such that $n = 2^m$, and for all $1 \le i \le 2n - 1$, $l_i = 2i$ and $r_i = 2i + 1$.