Background

WD spends all day immersed in matrices and cannot get out of it.

Problem Description

WD likes matrices very much, especially 01 matrices.

One day, CX gave WD a huge $n$-row, $m$-column 01 matrix. WD found that the XOR value of every row and every column of this matrix is $0$.

CX then asked, “WD, do you know how many 01 matrices have XOR value $0$ in every row and every column!?” WD of course does not know this, so he came to ask you.

Since the answer may be very large, you only need to output the result modulo $998\,244\,353$.

Input Format

The first line contains an integer $T$, which represents the number of test cases.

In the next $T$ lines, each line contains two integers $n, m$, representing the number of rows and columns in the query.

Output Format

Output $T$ lines. Each line contains one integer, the answer modulo $998\,244\,353$.

2
2 2
2 2018

2
851481696

Hint

• Subtask 1 (11 pts): $1\le T\le 10,~1\le n,m\le 4$.
• Subtask 2 (43 pts): $1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000$.
• Subtask 3 (46 pts): $1\le T\le 10^5,~1\le n,m\le 10^9$.

Translated by ChatGPT 5