PCK君が住むアイヅ町には、N個の地点と各地点をつなぐ$N-1$本の道があります。地点にはそれぞれ$1$から$N$までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。
株式会社IZUAのCEOであるPCK君は、日々の生活に変化を加えるため、ルーチンワークとして毎日通勤路を変えることにしています。
PCK君は、以下の条件を満たす経路で通勤します。
PCK君は自宅と会社の移転を検討していて、移転後に何通りの通勤路を楽しむことができるか知りたがっています。
地点の数、地点同士を直接つなぐ道の情報、移転後の自宅の最寄りの地点$u$と会社の最寄りの地点$v$が与えられる。ただし、$u$と$v$の組は質問としていくつか与えられる。各質問に対して、通勤路の数を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_{N-1}$ $t_{N-1}$
$Q$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_Q$ $v_Q$
１行目に地点の数$N$ ($2 \leq N \leq 100,000$)が与えられる。続く$N-1$行に、２つの地点を直接つなぐ道の情報が与えられる。$s_i$と$t_i$ ($1 \leq s_i < t_i \leq N$)は$i$番目の道がつなぐ２つの地点の番号である。ただし、どの２つの地点についても、それらを直接つなぐ道は１本以下とする。続く行に質問の数$Q$ ($1 \leq Q \leq 100,000$)が与えられる。続く$Q$行に各質問を表す２つの整数$u_i$と$v_i$ ($1 \leq u_i < v_i \leq N$)が与えられる。
質問ごとに、通勤路の数を998,244,353で割った余りを１行に出力する。
4 1 2 2 3 2 4 2 1 2 1 3
1 2