Nikuniku 想要为仓库制定一个安保计划。仓库可以表示为一个有 $n$ 行 $m$ 列的网格。左上角的单元格为 $(1, 1)$，右下角的单元格为 $(n, m)$。

安保计划是指在网格中选择一些单元格，并在每个被选中的单元格中放置一个摄像头。

当在单元格 $(i, j)$ ($1 \le i \le n, 1 \le j \le m$) 放置摄像头时，Nikuniku 可以选择一个单元格 $(p, q)$ ($1 \le p \le n, 1 \le q \le m$) 作为其参数。当且仅当以下两个条件同时满足时，单元格 $(x, y)$ 被该摄像头保护： 1. $\min(i, p) \le x \le \max(i, p)$ 2. $\min(j, q) \le y \le \max(j, q)$

注意，$(p, q)$ 不一定与 $(i, j)$ 不同，且一旦配置后就不能修改。不同的摄像头可以配置不同的参数。

一个安保计划是完美的，当且仅当所选的摄像头可以配置合适的参数，并且所有 $n \times m$ 个单元格都能被至少一个摄像头保护。

对于一个完美的安保计划，如果 Nikuniku 无法移除计划中的任何一个摄像头，并通过调整剩余摄像头的参数使计划依然保持完美，则称其为最小安保计划。

Nikuniku 想知道不同最小安保计划的数量。

当且仅当一个单元格在一个计划中被选中，而在另一个计划中未被选中时（无论参数如何），这两个计划被视为不同。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。 每个测试用例包含一行，包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^9$)，表示网格的大小。

输出格式

对于每个测试用例，输出一个整数，表示该测试用例的答案对 $998244353$ 取模的结果。

样例

输入 1

6
2 2
4 4
8 8
3 3
3 5
3 7

输出 1

4
129
78769
10
80
273