Description

After birth, the neural network of a Martian can be viewed as a forest consisting of several undirected trees $\{T_1(V_1, E_1), T_2(V_2, E_2), \dots, T_m(V_m, E_m)\}$. As the Martian ages, the number of neural connections grows. Initially, the set of grown connections $E^\star = \emptyset$. The neural network grows according to the following rule: * If nodes $u \in V_i$ and $v \in V_j$ belong to different undirected trees $T_i$ and $T_j$ ($i \neq j$), then $E^\star$ must contain the edge $(u, v)$.

Eventually, when no more neural connections can grow, the connections between nodes in the neural network can be viewed as an undirected graph $G(V, E)$, where $$V = V_1 \cup V_2 \cup \dots \cup V_m, E = E_1 \cup E_2 \cup \dots \cup E_m \cup E^\star.$$

Martian decision-making is accomplished by establishing loops in $G(V, E)$. For different external inputs, Martians establish different neural connection loops to make different responses. To understand the complexity of Martian behavioral patterns, JYY decided to calculate the number of Hamiltonian cycles in $G$.

A Hamiltonian cycle in $G(V, E)$ is a simple cycle that starts from the first node of the first tree, visits every other node in $V$ exactly once, and returns to the first node of the first tree.

Input

The first line contains an integer $m$, representing the number of undirected trees in the Martian neural network initially.

The next $m$ parts describe each tree $T_i$. For each $T_i$, the first line contains the number of nodes $k_i$ in the tree $T_i(V_i, E_i)$. Assume $V_i = \{v_1, v_2, \dots, v_{k_i}\}$. The next $k_i - 1$ lines each contain two integers $x, y$, representing an edge between nodes $v_x$ and $v_y$ ($1 \leq x, y \leq k_i$) in the tree, i.e., $(v_x, v_y) \in E_i$.

Output

Output a single non-negative integer representing the number of Hamiltonian cycles modulo $998244353$.

Examples

Input 1

2
3
1 2
1 3
2
1 2

Output 1

12

Note 1

In this example, there are a total of 5 nodes in $G$. Only the nodes 2 and 3 of the first tree do not have an edge between them; any other two nodes have an edge between them. The number of Hamiltonian cycles in such a graph is 12.

Examples 2

See neural/neural2.in and neural/neural2.ans in the contestant directory.

Subtasks