P15713 [JAG 2023 Summer Camp #2] Empty Quartz

$N$ crystals are aligned in a row. However, some of them may be phantoms. Jun counted the number of real crystals from $l$-th to $r$-th (closed interval) for every $l, r (1 \leq l \leq r \leq N)$ pair and recorded their evenness. His $\frac{N(N+1)}{2}$ records show that there were $K$ intervals that contained an odd number of real crystals. How many possible crystal alignments are there? Answer the remainder divided by $998244353$. Note that if there is $i$ such that the $i$-th crystal from the left is real on one side and phantom on the other, the two alignments are considered different. You are given $T$ of the above problems. Answer each of them.

$$ \begin{aligned} &T \\ &N_1 \ K_1 \\ &\vdots \\ &N_T \ K_T \end{aligned} $$ The input satisfies the following constraints. - All inputs consist of integers. - $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}$

Output $T$ lines. On the line $i$, answer the problem when $N = N_i, K = K_i$. Add a new line at the end of each line.

If we denote a real crystal as $1$ and an phantom as $0$, the following three alignments satisfy the condition at Sample Input 1. - $0, 1, 0$ - $1, 0, 1$ - $1, 1, 1$