题目描述

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

输入格式

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

输出格式

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

样例

input

1
1 2

output

340

数据范围与提示

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