1 is the past that has vanished like smoke.
2 is the present that passes in a flash.
3 is the future that is out of reach.
The confusion and worries of the past lead to the present. If the passion for your dreams has not changed, then you might as well treat your confusion and worries as valuable experience.
The present will eventually lead to the future. The door to the future must be hidden somewhere in the world. Although it may not be easily found, if you do not reach out your hands, you will never be able to touch it.
To create a brand new time starting from the present, you need to connect everyone. 1, 2, and 3 are all indispensable. Goals that cannot be achieved alone can surely be overcome by gathering the strength of many. Even if you have worked hard enough on your own, if you can each work twice as hard when connected, then you might as well be in the same boat and resonate with the same rhythm.
Given an $N \times M$ grid, find the number of ways to fill each cell with $1$, $2$, or $3$ such that there exists at least one way to connect adjacent cells sharing 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$.
Input
The input is read from standard input.
The first line contains a positive integer $T$, representing the number of test cases. It is guaranteed that $1 \le T \le 100$.
Each of the next $T$ lines contains two space-separated positive integers $N$ and $M$, representing the size of the grid. It is guaranteed that $1 \le N \le 3$ and $1 \le M \le 10^9$.
Output
Output to standard output.
For each test case, output a single line containing a non-negative integer representing the number of ways to fill the grid, modulo $998,244,353$.
Examples
Input 1
5
3 4
2 5
1 6
2 240117
3 378140683Output 1
280
0
4
451142875
980338319Note
It is not that meeting leads to parting, but that parting guides new meetings.