配点 : $1200$ 点

問題文

整数 $N,A$ が与えられます． $(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ であって，以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください．

• $P_1=A$
• 以下の操作を繰り返すことで，$P$ の要素数を $2$ にできる．- $3$ つの連続する要素 $x,y,z$ を選ぶ． ただしこの時，$y<\min(x,z)$ もしくは $y>\max(x,z)$ が成り立っている必要がある． そして，$y$ を $P$ から消す．
• $3$ つの連続する要素 $x,y,z$ を選ぶ． ただしこの時，$y<\min(x,z)$ もしくは $y>\max(x,z)$ が成り立っている必要がある． そして，$y$ を $P$ から消す．

一つの入力ファイルにつき，$T$ 個のテストケースに答えてください．

制約

• $1 \leq T \leq 5 \times 10^5$
• $3 \leq N \leq 10^6$
• $1 \leq A \leq N$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

$T$

$case_1$

$case_2$

$\vdots$

$case_T$

各テストケースは以下の形式で与えられる．

$N$ $A$

出力

各テストケースについて答えを出力せよ．

8
3 1
3 2
3 3
4 1
4 2
4 3
4 4
200000 10000

1
2
1
3
5
5
3
621235018

例えば，$N=4,A=2$ の時，$P=(2,1,4,3)$ は条件を満たします． 以下に手順の例を示します．

• $(x,y,z)=(2,1,4)$ を選び，$1$ を消す．$P=(2,4,3)$ になる．
• $(x,y,z)=(2,4,3)$ を選び，$4$ を消す．$P=(2,3)$ になる．