Eric has developed an iwanna game. Now he invites you to participate in a test of his game.

The game map can be viewed as an $$$n$$$-node tree, connected by $$$n-1$$$ weighted edges.

In a game, the player has to walk from the starting point $$$s$$$ to the finishing point $$$t$$$. As soon as the player moves to point $$$t$$$, the game ends. Since the player does not know where the end point is, the player will follow the following strategy: Assuming that the player is currently at point $$$x$$$, if there exists an unvisited neighboring node of point $$$x$$$, the player will randomly choose one of all the unvisited neighboring nodes to go to; otherwise, the player will go to the earliest visited node among its neighboring nodes.

The cost of a single game is the sum of the weights of the visited edges on the path (multiple passes of the same edge require multiple computations).

In order to test the game, Eric asks you q questions, giving you the starting point $$$s$$$ and the end point $$$t$$$ for each question. You need to answer the expected cost for each question, computed modulo $$$998244353$$$.