题目描述

整数 $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$ から消す．

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

输入格式

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

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

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

$N$ $A$

输出格式

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

题目大意

一个 $\{1, \dots, N\}$ 的排列 $P$ 是好的，当且仅当：

• $P_1 = A$，其中 $A$ 是一个给定常数。
• 可以通过施加一系列以下操作，将 $P$ 删除至只剩两个元素：选择连续的三个元素 $x, y, z$，满足 $y < \min\{x, z\}$ 或者 $y > \max\{x, z\}$，随后删除 $y$。

请你计数有多少长度为 $N$ 的好排列，对 $998244353$ 取模。

有 $T$ 组数据（$1\le T\le 10^5$），每组给出 $N, A$（$1\le A\le N\le 10^6$）。注意并不保证 $\sum N\le10^6$。

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

提示

制約

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

Sample Explanation 1

例えば，$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)$ になる．