说明

有 $N$ 个水晶排成一行。然而，其中一些可能是幻影。

Jun 对于每一对 $l, r (1 \leq l \leq r \leq N)$，统计了从第 $l$ 个到第 $r$ 个（闭区间）真实水晶的数量，并记录了其奇偶性。

他的 $\frac{N(N+1)}{2}$ 条记录显示，有 $K$ 个区间包含了奇数个真实水晶。有多少种可能的水晶排列方式？请输出答案除以 $998244353$ 的余数。

注意，如果存在某个 $i$，使得从左数第 $i$ 个水晶在一种排列中是真实的，而在另一种中是幻影，则这两种排列被认为是不同的。

你被给出了 $T$ 个上述问题。请回答每个问题。

输入格式

$$\begin{aligned} &T \\ &N_1 \ K_1 \\ &\vdots \\ &N_T \ K_T \end{aligned}$$

输入满足以下约束：

• 所有输入均为整数。
• $1 \leq T \leq 10^5$
• $1 \leq N_i \leq 10^5$
• $0 \leq K_i \leq \frac{N_i(N_i+1)}{2}$

输出格式

输出 $T$ 行。在第 $i$ 行，回答当 $N = N_i, K = K_i$ 时的问题。请在每行末尾添加换行符。

1
3 4

3

5
5 9
6 10
10 24
10 25
100000 75915540

10
21
165
0
651081880

提示

如果我们用 $1$ 表示真实水晶，用 $0$ 表示幻影，那么以下三种排列满足样例输入 1 的条件：

• $0, 1, 0$
• $1, 0, 1$
• $1, 1, 1$

翻译由 DeepSeek V3.2 完成