E. BABA IS LOCKED
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a grid with $$$n$$$ rows and $$$m$$$ columns. In one move, you can move up, left, or right (not down), as long as you stay within the grid and never visit any square more than once.

How many ways are there to get from the bottom-left square to the top-right square?

Since the answer may be large, output it modulo $$$998 \, 244 \, 353$$$.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 100$$$) — the number of rows and columns in the grid, respectively.

Note that there is no limit on the sum of $$$n$$$ or $$$m$$$ over all test cases.

Output

For each test case, print a single integer — the number of ways to get from the bottom-left square to the top-right square, modulo $$$998 \, 244 \, 353$$$.

Example
Input
2
2 3
3 4
Output
3
16
Note

In the first test case, there are $$$3$$$ possible paths: