H. 网格路径
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于任意两个正偶数 $$$h$$$ 和 $$$w$$$，定义 $$$f(h, w)$$$ 如下。

考虑一个 $$$h$$$ 行 $$$w$$$ 列的方格矩形，将每个方格视为一个顶点；如果两个方格有一条公共边，就在对应的两个顶点之间连一条无向边。由此得到一张 $$$h \times w$$$ 的网格图。

现在选择一个「子矩形」（即连续若干行与连续若干列交叉形成的方格区域），要求它不等于整个网格，删除其中的所有方格，以及与这些方格相连的所有边。

如果删除后剩余的网格图中存在一条恰好经过每个剩余顶点各一次的路径（起点和终点可以任意选择），则称这次删除是「合法」的。

$$$f(h, w)$$$ 表示 $$$h \times w$$$ 的网格中「合法」的删除方案的数量。两个删除方案不同，当且仅当它们所属的网格尺寸不同，或者删除的「子矩形」不同。

给定两个正偶数 $$$n$$$ 和 $$$m$$$，请你计算：

$$$$$$ \sum_{\substack{2 \le h \le n \\ h \text{ 为偶数}}} \sum_{\substack{2 \le w \le m \\ w \text{ 为偶数}}} f(h, w) $$$$$$

由于答案可能很大，请输出答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \le T \le 2 \times 10^5$$$），表示测试用例的数量。对于每组测试用例：

  • 仅一行，包含两个正偶数 $$$n$$$ 和 $$$m$$$（$$$2 \le n, m \le 10^9$$$），含义如题面所述。
Output

对于每组测试用例，输出一行，包含一个整数，表示答案对 $$$998 \, 244 \, 353$$$ 取模后的结果。

Example
Input
4
2 2
2 4
4 4
6 6
Output
8
34
153
1069
Note

对于第一组测试用例，需要统计的网格尺寸只有 $$$2 \times 2$$$ 一种。$$$2 \times 2$$$ 的网格共有 $$$9$$$ 个「子矩形」，其中删除整个网格不被允许；而其余 $$$8$$$ 种删除均「合法」——删除后剩余的方格要么是三个方格组成的 L 形，要么是两个相邻的方格，都存在满足条件的路径。因此 $$$f(2, 2) = 8$$$，答案为 $$$8$$$。

对于第二组测试用例，需要统计的网格尺寸为 $$$2 \times 2$$$ 和 $$$2 \times 4$$$，答案为：$$$f(2, 2) + f(2, 4) = 8 + 26 = 34$$$。

对于第三组测试用例，需要统计的网格尺寸为 $$$2 \times 2$$$、$$$2 \times 4$$$、$$$4 \times 2$$$、$$$4 \times 4$$$，答案为：$$$f(2, 2) + f(2, 4) + f(4, 2) + f(4, 4) = 8 + 26 + 26 + 93 = 153$$$。

对于第四组测试用例，在第三组测试用例的基础上还需要统计 $$$2 \times 6$$$、$$$4 \times 6$$$、$$$6 \times 2$$$、$$$6 \times 4$$$、$$$6 \times 6$$$ 这五种尺寸，答案为：$$$153 + f(2, 6) + f(4, 6) + f(6, 2) + f(6, 4) + f(6, 6) = 153 + 52 + 196 + 52 + 196 + 420 = 1069$$$。