Winning Configuration Count in Alternating Black‐White Game

You are playing a turn‐based board game against an AI using two colors (black and white). The game is played on an (n \times m) board. Both you and the AI take turns placing a piece (of either color) on a cell that has not been used before until the board is completely filled. After that, the scores are computed as follows:

For each entire row or column, if the colors in that row (or column) are not all identical, you gain (1) point; if they are all identical, the AI gains (1) point. You win the game if and only if your total score is odd and the AI’s total score is even. Otherwise, the AI wins.

You play (T) independent games. In the (i)th game the board size is (n \times m). Two final board configurations are considered different if there is at least one cell that has a different color.

Your task is to compute, for each game, the number of final board configurations (i.e. assignments of black/white to each cell) that result in your victory. Since the answer may be very large, output it modulo (998244353).

A key observation is that if we denote the total number of rows and columns by (n+m) and define the number of lines (rows or columns) that are uniform (i.e. all cells with the same color) as (u) and non‐uniform as (n+m-u), then your winning condition (player score odd and AI score even) translates into: [ \begin{cases} (n+m - u) \equiv 1 \pmod{2},\ u \equiv 0 \pmod{2}. \end{cases} ] Since (n+m = u + (n+m-u)), one may check that a necessary (and sufficient) condition is that (n+m) is odd.

It turns out that the answer can be expressed by the formula below. Let [ A = 2^{n \cdot m} \quad\text{and}\quad B = 2^{-,(n+m-1)} \cdot (2^m-4)^n \cdot (2^n-4)^m, \quad ] where the exponents and inverses are computed modulo (998244353) (and the inverse of any number (x) is defined as (x^{998244353-2}) by Fermat's little theorem). Then, if (n+m) is odd the answer is [ \text{answer} = \frac{A + B}{2} \pmod{998244353}, ] otherwise the answer is (0).

Note: In the implementations below, careful modular exponentiation is required since exponents such as (n\cdot m) might be huge. In languages like C/C++/Java, you may need to reduce the exponent modulo (998244353-1) (by Fermat’s little theorem) when computing base powers modulo (998244353).

inputFormat

The first line contains a single integer (T) ((1 \le T \le 10^5)) denoting the number of test cases. Each of the next (T) lines contains two integers (n) and (m) ((1 \le n, m \le 10^9)) representing the dimensions of the board.

outputFormat

For each test case, output one integer: the number of final board configurations (modulo (998244353)) that result in your victory.

sample

4
1 1
1 2
2 1
2 2

2
2
2
0