题目背景

充分必要，切比雪夫。

原来还是，不需要了。

题目描述

一个 $n\times m$ 的棋盘，对每个格子染上黑白两色之一。

询问有多少种染色方式，使得不存在横、竖、斜连续四个格子中存在至少三个相同颜色的格子，并且不存在横、竖、斜连续三个格子的颜色相同。

若设棋盘的左上角为 $(1,1)$，右下角为 $(n,m)$，则称 $\{(x,y),(x+1,y),(x+2,y)\}$ 为横的连续三个格子，$\{(x,y),(x,y+1),(x,y+2)\}$ 为竖的连续三个格子、$\{(x,y),(x+1,y+1),(x+2,y+2)\}$ 和 $\{(x,y),(x+1,y-1),(x+2,y-2)\}$ 为斜的连续三个格子（以上格子均在棋盘内）。

连续四个格子同理。

输入格式

本题有多组数据。

第一行一个整数 $T$ 表示数据组数。
接下来 $T$ 行，每行两个整数 $n,m$ 表示一次询问。

输出格式

共 $T$ 行，每行一个整数表示答案。答案对 $998244353$ 取模。

1
2 2

16

1
3 3

32

提示

样例解释

样例 $1$：显然任意染色均合法，答案为 $2^4=16$。

样例 $2$：

101
110
010

这是合法方案之一。

111
110
011

这是不合法方案之一，因为 $\{(1,1),(1,2),(1,3)\}$、$\{(1,2),(2,2),(3,2)\}$ 和 $\{(1,1),(2,2),(3,3)\}$ 均不满足条件。

数据规模

本题采用捆绑测试。 | $\text{Subtask}$ | $n,m\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $30$ | $40$ | | $2$ | $10^9$ | $60$ |

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 10^9$。