Background

Sufficient and necessary, Chebyshev.

Originally yes, but no longer needed.

Problem Description

Given an $n \times m$ chessboard, color each cell with one of two colors: black or white.

Count how many colorings satisfy both of the following:

• Among any 4 consecutive cells in a horizontal, vertical, or diagonal line, there do not exist at least 3 cells with the same color.
• Among any 3 consecutive cells in a horizontal, vertical, or diagonal line, the colors are not all the same.

Let the top-left corner be $(1,1)$ and the bottom-right corner be $(n,m)$. Then:

• $\{(x,y),(x+1,y),(x+2,y)\}$ is a set of 3 consecutive horizontal cells.
• $\{(x,y),(x,y+1),(x,y+2)\}$ is a set of 3 consecutive vertical cells.
• $\{(x,y),(x+1,y+1),(x+2,y+2)\}$ and $\{(x,y),(x+1,y-1),(x+2,y-2)\}$ are sets of 3 consecutive diagonal cells.

All the above cells must lie inside the board.

The definition for 4 consecutive cells is analogous.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.
The next $T$ lines each contain two integers $n, m$, representing one query.

Output Format

Output $T$ lines, each containing one integer: the answer. Take the answer modulo $998244353$.

1
2 2

16

1
3 3

32

Hint

Sample Explanation

Sample $1$: Clearly, any coloring is valid, so the answer is $2^4 = 16$.

Sample $2$:

101
110
010

This is one valid coloring.

111
110
011

This is one invalid coloring, because $\{(1,1),(1,2),(1,3)\}$, $\{(1,2),(2,2),(3,2)\}$, and $\{(1,1),(2,2),(3,3)\}$ all do not satisfy the conditions.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le T \le 10^5$, $1 \le n,m \le 10^9$.

Translated by ChatGPT 5