Feifei is writing a problem about lollipops. He is currently working on a problem involving the Lowest Common Ancestor (LCA) of two nodes in a rooted tree. The problem is as follows:

Given a rooted tree with $n$ nodes, where the root is node $1$. You need to answer $m$ queries. Each query provides two node indices $x$ and $y$ in the tree. You need to output the index of their Lowest Common Ancestor (LCA) in the tree.

Feifei thinks this problem is too simple, so he decides to add a bug to the code. Below is Feifei's depth-first search implementation:

DFS(u, Parent)
1 for each v adjacent to u
2     do if v != Parent
3         then Fa[v][0] <- u
4             Dep[v] <- Dep[u] + 1
5             DFS(v, u)

Feifei thinks this depth-first search is correct, but it lacks his unique style. So he changes it to the following implementation:

DFS(u, Parent)
1 for each v adjacent to u
2     do if v != Parent
3         then Fa[v][0] <- u
4             Dep[v] <- Dep[u] + RANDOM(0..1)
5             DFS(v, u)

Where RANDOM(0..1) is a function that returns an element from the set $\{0, 1\}$ with equal probability.

To avoid discrepancies caused by different implementations of the rest of the algorithm, Feifei provides the following pseudocode for the other parts of the problem. Of course, since this uses a common implementation that is consistent with most people's habits, the following code is for reference only.

MAIN
1 INIT // Read and build adjacency list
2 DFS(1, 0)
3 for j <- 1 to [log2 n]
4     for i <- 1 to n
5         do Fa[i][j] <- Fa[Fa[i][j - 1]][j - 1]
6 for i <- 1 to m
7     do print GET-LCA(query_i.x, query_i.y)

In the MAIN function above, query_i.x and query_i.y represent the two node indices $x$ and $y$ for the $i$-th query, respectively. The GET-LCA function called is implemented as follows:

GET-LCA(x, y)
1 if Dep[x] < Dep[y]
2     then SWAP(x, y)
3 delta <- Dep[x] - Dep[y]
4 for i <- [log2 n] downto 0
5     do if 2^i <= delta
6         then x <- Fa[x][i]
7             delta <- delta - 2^i
8 if x = y
9     then return x
10 for i <- [log2 n] downto 0
11     do if Fa[x][i] != Fa[y][i]
12         then x <- Fa[x][i]
13             y <- Fa[y][i]
14 return Fa[x][0]

Feifei is satisfied with this modified code and rewards himself with a limited-edition giant lollipop. Obviously, this new code has a certain probability of passing the original problem. However, when Feifei submitted this code to the OJ, the result returned was Wrong Answer. He is very unconvinced, but has nothing to say. He wants to know, for each query given in the problem, what is the probability that the correct answer is output.

Since Feifei does not like fractions, he wants you to output the answer modulo $998244353$ ($7 \times 17 \times 2^{23} + 1$, a prime number).

For a rational number, it can always be expressed in the form $\frac{a}{b}$, where $a \ge 0, b > 0$, and $\gcd(a, b) = 1$. For a prime $p$, if $b$ is not a multiple of $p$, we can define $\frac{a}{b} \pmod p$ as the smallest non-negative integer $x$ such that $bx \equiv a \pmod p$. If $b$ is a multiple of $p$, then $\frac{a}{b} \pmod p$ is undefined.

It is guaranteed that the answer modulo $998244353$ is defined.

Input

The first line contains an integer $n$, representing the size of the tree. The next $n-1$ lines each contain two integers $x, y$, describing an edge in the tree. The next line contains an integer $m$, representing the number of queries. The next $m$ lines each contain two integers $x, y$, describing a query.

It is guaranteed that the given graph is a tree and $1 \le x, y \le n$.

Output

Output $m$ lines, each containing the answer for the corresponding query.

This represents the probability that the program written by Feifei outputs the correct answer for the query, considering only that query.

All probabilities must be output modulo $998244353$!

Examples

Input 1

3
1 2
1 3
2
3 1
3 2

Output 1

499122177
499122177

Input 2

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

Output 2

748683265
499122177
748683265

Subtasks

For all data, $1 \le n, m \le 2 \times 10^5$.