Description

$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.

Input Format

$$\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 Format

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.

1
3 4

3

5
5 9
6 10
10 24
10 25
100000 75915540

10
21
165
0
651081880

Hint

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$