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.