纽约市警察局（NYPD）正在制定一项曼哈顿街区的巡逻计划。

该街区可以表示为一个由正方形方格组成的 $n \times m$ 网格，坐标从 $(1, 1)$ 到 $(n, m)$。每个方格由一名特定的警员巡逻。出于培训目的，NYPD 偶尔会想要重新分配警员到不同的方格。然而，为了保持现有的协作关系，他们希望保持任意两名警员之间的曼哈顿距离不变。

更正式地，设 $(x_1, y_1)$ 和 $(x_2, y_2)$ 为两名警员的初始坐标，$(x'_1, y'_1)$ 和 $(x'_2, y'_2)$ 为重新分配后他们的最终坐标。那么，必须满足以下条件：

$$|x_1 - x_2| + |y_1 - y_2| = |x'_1 - x'_2| + |y'_1 - y'_2|$$

问有多少种可能的警员到方格的分配方案，能够保持两两之间的曼哈顿距离不变？

如果某位警员被移动到了不同的方格，则认为两种分配方案是不同的。警员允许留在原始位置。由于答案可能很大，请输出其对 $998244353$ 取模后的余数。

输入格式

本题包含 $T$ 组独立的测试数据。

第一行包含一个整数 $T$ ($1 \le T \le 10^4$) — 表示需要处理的独立测试数据组数。

接下来的 $T$ 行，每行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5000$) — 表示街区网格的维度。

输出格式

对于每组测试数据，输出一行一个整数 — 保持两两曼哈顿距离不变的警员分配方案数模 $998244353$ 的余数。

样例

输入样例 1

2
1 1
2 3

输出样例 1

1
4

说明

在第一组测试数据中，对于 $1 \times 1$ 的网格，只有一种分配方案。

在第二组测试数据中，对于 $2 \times 3$ 的网格，有 4 种有效的分配方案。其中两种如下图所示。右侧显示了一种无效的分配方案：警员 2 和 5 之间的距离从 1 变成了 3。