P8933 [JRKSJ R7] Skillful Block Fast Recurrence

Sufficient and necessary, Chebyshev. Originally yes, but no longer needed.

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.

**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 $T$ lines, each containing one integer: the answer. Take the answer modulo $998244353$.

### 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. | $\text{Subtask}$ | $n,m\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $30$ | $40$ | | $2$ | $10^9$ | $60$ | For $100\%$ of the testdata, $1 \le T \le 10^5$, $1 \le n,m \le 10^9$. Translated by ChatGPT 5