Background

1 is the past that has vanished like smoke.

2 is the present that passes in an instant.

3 is the distant future.

The confusion and worries of the past lead to the present. If the passion for your dreams has not changed until now, then you may treat that confusion and those worries as valuable experience.

The present will also lead to the future. The gate to the future must be hidden somewhere in a corner of the world. Although it may not be easy to find, if you do not reach out your hands, you will never be able to touch it.

To create a brand-new time starting from now, you need to connect everyone together. 1, 2, and 3 are all indispensable. Goals that cannot be achieved alone can surely be overcome by gathering everyone’s strength. Even if you have fought hard enough when you were all by yourself, if each person can work twice as hard when connected together, then let us get through it in the same boat, in the same rhythm.

Problem Description

Given an $N\times M$ grid, count the number of ways to fill each cell with $1$, $2$, or $3$, such that after filling, there exists at least one way to connect pairs of cells that share a common edge, satisfying:

• Each cell filled with $1$ or $3$ is connected to exactly one adjacent cell filled with $2$.

• Each cell filled with $2$ is connected to exactly one adjacent cell filled with $1$ and exactly one adjacent cell filled with $3$, respectively.

Input Format

The first line contains a positive integer $T$, representing the number of test cases in this test point. It is guaranteed that $1\le T\le 100$.

The next $T$ lines each contain two positive integers $N$ and $M$ separated by spaces, representing the size of the grid. It is guaranteed that $1\le N\le 3$, $1\le M\le 10^9$.

Output Format

For each test case, output one line containing a non-negative integer, representing the number of valid fillings modulo $998,244,353$.

5
3 4
2 5
1 6
2 240117
3 378140683

280
0
4
451142875
980338319

Hint

It is not meeting that brings separation, but separation that guides the next meeting.

Source and Acknowledgements

From the finals of THUPC2024 (Tsinghua University Programming Contest and Collegiate Invitational Contest 2024). Thanks to THUSAA for providing this problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository: https://thusaac.com/public

Translated by ChatGPT 5