Problem Statement

$N$ quartz crystals are arranged in a row. However, some of them may be illusions with no physical substance.

For every pair $l,r (1 \le l \le r \le N)$, Jun counted the number of crystals with physical substance from the $l$-th through the $r$-th (closed interval) and recorded its parity.

According to his $\frac{N(N+1)}{2}$ records, there were $K$ intervals containing an odd number of crystals with substance. How many arrangements of the crystals are possible? Find the answer modulo $998244353$.

Here, two arrangements are considered different if there exists some $i$ such that the $i$-th crystal from the left has substance in one arrangement and has no substance in the other.

You are given $T$ instances of the above problem. Answer each of them.

Input

$T$
$N_1\ K_1$
$\vdots$
$N_T\ K_T$

• All inputs are integers
• $1 \le T \le 10^5$
• $1 \le N_i \le 10^5$
• $0 \le K_i \le \frac{N_i(N_i+1)}{2}$

Output

Print $T$ lines. On the $i$-th line, print the answer to the problem for $N = N_i, K = K_i$.
Print a newline at the end of each line.

Sample

1
3 4

3

5
5 9
6 10
10 24
10 25
100000 75915540

10
21
165
0
651081880