注意

この問題は、 A DELETEQ の強化版です。入出力の形式が異なることに注意してください。

問題文

あなたは、$x$ 個の文字列"AB"と、$y$ 個の文字列"BA"を持っています。

あなたは、この $x+y$ 個の全ての文字列を好きな順番で並べて連結します。(連結後の文字列を $S$ とします。)その後、以下の操作を $0$ 回以上の任意の回数行います。

• $S$ の連続する $2$ 文字で、等しい文字のペアを選び、選んだ $2$ 文字を $S$ から削除する。その後、残った前後の文字列を元の順番で連結する。

操作後、残った文字列 $S$ として考えられるものは何通り存在しますか。場合の数を $998244353$ で割った余りを答えてください。

なお、操作後の文字列 $S$ が空文字列になりうる場合、空文字列も $1$ 通りとして数えます。

この問題が $Q$ 個与えられるので、そのそれぞれに関して答えを求めてください。

入力

$Q$
$x_1{y}_1$
$...$
$x_Q{y}_Q$

• 入力は全て整数
• $1\le Q\le 2\times {10}^5$
• $1\le x_i\le 4000$
• $1\le y_i\le 4000$

出力

$i$ 行目には、 $x=x_i,y=y_i$ の場合の答えを出力し、改行してください。

サンプル

1
1 1

5

2
3 1
4000 4000

11
622937044