Problem Description

While carrying out a task, Accelerator connected to a temporary Misaka Network consisting of $n$ Misaka Sisters, numbered from Misaka $10032$ to Misaka $10031+n$. Each Misaka Sister holds some information, and to ensure storage efficiency, the information held by different sisters is pairwise distinct.

The temporary Misaka Network has two types of connections, $T_1$ and $T_2$, each forming a tree structure.

Due to computational needs, the sisters sometimes need to exchange information. Specifically, if two Misaka Sisters are connected by both types of connections at the same time, then they can swap the information they hold (they do not keep their original information). At the same time, they will swap their connections in $T_2$ (i.e., if the other Misaka Sister has a type-2 connection to some sister, that connection becomes owned by the first one instead, and vice versa).

Last Order is curious about how many different states of information possession are possible. Two states are considered different if and only if there exists at least one Misaka Sister whose possessed information differs between the two states.

She imagined several possible network configurations, and wants to compute the answer to the above question for each configuration (since these are imagined, it is not necessarily guaranteed that $n \le 9969$).

The Misaka Network computed the answer within 1 second, but for fun, Last Order wants you to help verify it. You need to output the number of states modulo $998244353$.

Simplified statement:

Given two unrooted trees $T_1, T_2$ on $n$ nodes, labeled $1 \sim n$.

There is a permutation $p$ of $1 \sim n$, initially $p_i = i$. You may perform the following operation any number of times:

Choose two nodes $u, v$ such that $u, v$ are adjacent in $T_1$, and $p_u, p_v$ are adjacent in $T_2$. Then swap $p_u$ and $p_v$.

How many distinct permutations $p$ can be obtained? Output the answer modulo $998244353$.

There are $t$ test cases.

Input Format

The first line contains an integer $t$, the number of test cases.

Then for each test case:

Line 1 contains an integer $n$, the number of Misaka Sisters in the temporary Misaka Network.

Lines $2 \sim n$ (a total of $n-1$ lines) each contain two integers $u, v$, indicating an edge between Misaka $10031+u$ and Misaka $10031+v$ in $T_1$.

Lines $n+1 \sim 2n-1$ (a total of $n-1$ lines) each contain two integers $u, v$, indicating an edge between Misaka $10031+u$ and Misaka $10031+v$ in $T_2$.

Output Format

Output $t$ lines. The $i$-th line should contain one integer: the answer for the $i$-th test case modulo $998244353$.

Example

Sample Input 1

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

Sample Output 1

8

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases within a single test file.

For all data:

• $1 \le t \le 10^5$
• $1 \le n \le 10^6$
• $\sum n \le 2 \times 10^6$
• $1 \le u, v \le n$
• $T_1$ and $T_2$ are guaranteed to be trees.

It is recommended to use fast input methods.