题目描述

蜜蜂小 B 拥有一个正二十面体结构的蜂巢，该蜂巢的 20 个面各自对应一种独特的气味（即共有 20 种不同气味）。根据正二十面体的几何特性，其每个面均与 5 个其他面相邻（正二十面体共 30 条棱，20 个正三角形面，每个面通过棱连接 5 个相邻面）。

小 B 发现了若干由格子组成的网格，网格的每个格子都被赋予一种气味（气味仅从上述 20 种中选取）。小 B 定义一个网格为「特殊网格」，当且仅当：

网格中存在两个横向或斜向相邻的格子（即 8 邻域相邻），且这两个格子的气味在正二十面体蜂巢上对应的面不相邻。

现在请你计算：共有多少种 n 行 m 列的网格属于「特殊网格」？

输入格式

1. 第一行输入一个正整数 t，表示测试数据的组数。

2. 接下来 t 行，每行输入两个正整数 n、m，分别表示一组询问中网格的行数和列数。

输出格式

对于每组询问，输出一行整数，表示 n 行 m 列的特殊网格数量，结果需对 998244353 取模。

样例

输入

1
1 2

输出

340

样例解析：1×2 网格的总可能数为 20×20=400 种。非特殊网格需满足两个格子气味对应相邻面，共 20×5=60 种。因此特殊网格数为 400-60=340，与输出一致。

数据范围

• 1 ≤ t ≤ 1000（测试数据组数）

• 1 ≤ n, m ≤ 10⁹（网格的行、列数）

• min(n, m) ≤ 5（网格的最小维度不超过 5）