题目描述

你在和 AI 下『连子棋』！你们有黑白两个颜色的棋子。

这盘棋的规则是：双方轮流下棋，棋子放满整个棋盘后，再来统计分数。如果每有一整行或一整列颜色 不完全相同，那么你就获得 $1$ 分。如果每有一整行或一整列颜色 完全相同，那么 AI 就获得 $1$ 分。当你的分数为奇数且 AI 的分数为偶数时，那么你就胜利了！否则，AI 胜利。

你和 AI 对弈了 $T$ 局，第 $i$ 局的棋盘大小为 $n\times m$。双方每一回合都可以选择下黑或者下白，下棋的位置不能和之前重复。那么请计算棋盘最终形态的方案数使得你能获胜。

两种下棋方式不同，当且仅当最终棋盘的形态不同，即棋盘上存在一个位置，使得两种棋盘在此位置的颜色不同。答案可能很大，请对 $998244353$ 取模。

输入格式

第一行一个整数 $T$，代表你和 AI 对弈的局数。

接下来有 $T$ 行，每行两个整数 $n,m$，表示棋盘的大小为 $n\times m$。

输出格式

输出 $T$ 行整数，第 $i$ 行整数表示第 $i$ 局你获胜的方案数。

5
2 2
2 3
2 5
4 3
4 5

0
32
512
2240
608864

4
1000 999
1000000 999999
999999 1000000
677777 66778

163503730
154415889
154415889
127032970

提示

【样例解释 $\mathbf 1$】

对于第 $2$ 局棋盘大小 $2\times 3$ 有下列两种棋盘形式（总共 $32$ 种棋盘形式，不一一列出）：

上面两种情况，你获得 $3$ 分，AI 获得 $2$ 分，故你获胜。

---

【数据规模与约定】

本题开启子任务捆绑测试。本题自动开启 O2 优化。

• Subtask 1（15 pts）：$2\leq n,m\leq 4$。
• Subtask 2（15 pts）：$2\leq n,m\leq 6$。
• Subtask 3（8 pts）：$2\leq n,m\leq 20$。
• Subtask 4（8 pts）：$2\leq n,m\leq 100$。
• Subtask 5（10 pts）：$2\leq n,m\leq 1000$。
• Subtask 6（44 pts）：$2\leq n,m\leq 10^6$。

对于所有测试点满足 $1\leq T\leq 5$，$2\leq n,m\leq 10^6$。