master is very interested in summation on trees. He has generated a rooted tree and wants to perform multiple queries, each asking for the sum of the $k$-th powers of the depths of all nodes on a path in the tree. The value of $k$ may be different for each query. Here, the depth of a node is defined as the number of edges on the path from the node to the root. He has handed this problem to pupil, but pupil cannot handle such complex operations. Can you help him solve it?

Input

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The next $n-1$ lines each contain two space-separated positive integers $i, j$, representing an edge connecting node $i$ and node $j$ in the tree.

The next line contains a positive integer $m$, representing the number of queries.

Each of the following lines contains three space-separated positive integers $i, j, k$, representing a query for the sum of the $k$-th powers of the depths of all nodes on the path from node $i$ to node $j$. Since this result can be very large, output the result modulo $998244353$.

The nodes of the tree are numbered starting from $1$, where node $1$ is the root of the tree.

Output

For each query, output a single line containing a positive integer representing the result modulo $998244353$.

Examples

Input 1

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

Output 1

33
503245989

Note

Let $d(i)$ denote the depth of the $i$-th node. For the tree in the example, we have $d(1) = 0, d(2) = 1, d(3) = 1, d(4) = 2, d(5) = 2$. Therefore, the answer to the first query is $(2^5 + 1^5 + 0^5) \pmod{998244353} = 33$, and the answer to the second query is $(2^{45} + 1^{45} + 2^{45}) \pmod{998244353} = 503245989$.

Subtasks

For 30% of the data, $1 \le n, m \le 100$. For 60% of the data, $1 \le n, m \le 1000$. For 100% of the data, $1 \le n, m \le 300000, 1 \le k \le 50$.

Note

The data scale is large; please be mindful to use efficient input and output methods.