题目描述

蜜蜂小 B 有一个正二十面体的蜂巢，它的每一面都有一个独特的气味，现在它发现了若干网格，对于每个网格，每个格子都有一种气味（属于以上二十种之一），小 B 认为一个网格是特殊的，当且仅当网格中存在两个格子横向或斜向相邻，它们的气味在蜂巢上对应的格子却不相邻，现在小 B 想知道有多少种 $n$ 行 $m$ 列的特殊的网格。

输入格式

第一行一个正整数 $t$ 表示测试数据组数。
接下来 $t$ 行每行两个正整数 $n, m$ 表示一组询问。

输出格式

对每个询问输出一行，表示答案对 $998244353$ 取模。

样例

1
1 2

340

数据范围与提示

$1 \leq t \leq 1000; n, m \leq 10 ^ 9; \min(n, m) \leq 5$