Matrix Game

Problem Description

Little S is playing a game: he has a board of length $N$ and width $M$, in which some cells are black (the rest are white).

In one operation he may choose a rectangular region whose length and width are both greater than $1$; if exactly $3$ of its four corner cells are black, he may paint the remaining white corner cell black.

Find how many different $N \times M$ boards satisfy both:

• Little S can turn the entire board black after a finite number of operations;
• the number of black cells used is minimal.

Two boards are different if and only if there exists at least one cell with a different color in the two boards. Output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains two positive integers $N$ and $M$.

Constraints: for all data, $1 \le T \le 100$, $1 \le N \le 100$, $1 \le M \le 100$.

Output Format

For each test case, output one integer on a single line: the answer.

Sample Input

2
1 1
2 2

Sample Output

1
4