Empty Quartz

Time limit2sMemory limit1024 MB

Summary

Count the 0/1 strings of length N where exactly K intervals contain an odd number of 1s, modulo 998244353, for T queries.

Level: Medium5 of 10
Topics: Combinatorics, Prefix sum, Math
Solved: No attempts yet

Problem

$N$ crystals are aligned in a row. Some of them may be phantoms.

Jun counted the real crystals in every interval $[l, r]$ with $1 \le l \le r \le N$ and recorded whether each count was even or odd.

His $\frac{N(N+1)}{2}$ records show that there were $k$ intervals containing an odd number of real crystals. How many possible crystal alignments are there? Output the answer modulo $998244353$ .

If the $i$ -th crystal from the left is real in one alignment and a phantom in the other, the two alignments are considered different.

You are given $T$ problems. Answer each of them.

Input

The first line contains $T$ . Each of the next $T$ lines contains $N_i$ and $K_i$ .

Output

Output $T$ lines. On line $i$ , print the answer for $N = N_i$ and $K = K_i$ .

Hint

Write a real crystal as 1 and a phantom as 0. For $N = 3$ and $K = 4$ , the valid alignments are the following three.

0, 1, 0
1, 0, 1
1, 1, 1

Examples2

Example 1
Input
```
1
3 4
```
Expected output
```
3
```

Example 2

Input

5
5 9
6 10
10 24
10 25
100000 75915540

Expected output