Marisa 想要为 Alice 建造一个 $n \times m$ 的矩形游泳池。为此，Marisa 可以在无限的二维网格上选择四个整点，并施展魔法。例如，下图展示了建造 $5 \times 5$ 游泳池的三种可能方式。

Marisa 很快发现，由于游泳池的四条边可以不平行于坐标轴，因此建造游泳池的方法有很多种。这里，两种建造方式被视为不同，当且仅当其中一种方式下的游泳池无法通过平移（不进行旋转和翻转）变换为另一种方式下的游泳池。现在，Marisa 对所有可能方式下，完全位于游泳池内部的 $1 \times 1$ 正方形的总数感到好奇。由于结果可能非常大，你需要将其对 $998\,244\,353$ 取模后输出。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

每个测试用例占一行，包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^{18}$)，表示游泳池的尺寸。

保证最多有 $10$ 个测试用例满足 $\max(n, m) > 10^9$。

输出格式

对于每个测试用例，输出一个数字，表示所有可能方式下，完全位于游泳池内部的 $1 \times 1$ 正方形的总数（对 $998\,244\,353$ 取模）。

样例

输入格式 1

5
5 5
2 3
5 10
2197525579 1145141
91 65

输出格式 1

51
12
228
438744975
34722

说明

如图所示，建造游泳池恰好有三种不同的方式。这三种方式中，完全位于游泳池内部的 $1 \times 1$ 正方形数量分别为 $25$、$13$ 和 $13$。因此总数为 $51$。