You are given a tree that contains $n$ vertices and $q$ queries. Each query is determining the number of decompositions of the tree into paths and the path from $v$ to $u$ that is one of the paths in the decomposition modulo $998244353$.

A tree decomposition in paths is valid if each vertex belongs to exactly one path. A path can be a single vertex. Two decompositions are different if there are two vertices $v$ and $u$ that belong to the same path in one of the decompositions but two distinct paths in the other.

Input format

• The first line contains $n$ denoting the number of vertices in the tree.
• Each of following $n-1$ lines contains space-separated integers $v_i, u_i$ describing the tree's $i^{th}$ edge's vertex ($v_i, u_i$).
• Each of following $q$ lines contains space-separated integers $v, u$ describing the $i^{th}$ query's path that is from $v$ to $u$ ($v$ and $u$ can be equal).

Output format

For each query, print the answer of a specific query in a line.

Constraints

$1 \leq n, q \leq 10^5$

$1 \leq v_i, u_i \leq n$

It is guaranteed that the edges form a tree.