The NYPD is making a plan for patrolling a neighborhood of Manhattan.
The neighborhood can be represented by a $$$n \times m$$$ grid of square blocks with coordinates from $$$(1, 1)$$$ to $$$(n, m)$$$. Each block is patrolled by one particular officer. For training purposes, every once in a while the NYPD wants to change assignments of officers to blocks. However, to maintain the existing cooperations, they want to preserve the Manhattan distance between each pair of officers.
More formally, let $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ be the initial coordinates of two officers, and $$$(x_1', y_1')$$$ and $$$(x_2', y_2')$$$ be their final coordinates after reassignment. Then, the following must hold: $$$|x_1-x_2|+|y_1-y_2| = |x_1'-x_2'| + |y_1'-y_2'|$$$.
How many possible assignments of officers to blocks are there which preserve the pairwise Manhattan distances?
Two assignments are considered different if some officer is moved to a different block. The officers are allowed to stay in original positions. Since the answer might be large, output its remainder modulo $$$998244353$$$.
The problem consists of $$$T$$$ independent test cases.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of independent test cases to process.
Each of the next $$$T$$$ lines contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 5000$$$) — the dimensions of the neighborhood grid.
For each test case, output a single line — the number of assignments of officers to blocks which preserve the pairwise Manhattan distances modulo $$$998244353$$$.
21 12 3
1 4
In the first test case, there is only one assignment for a $$$1 \times 1$$$ grid.
In the second test case, there are 4 valid assignments for a $$$2 \times 3$$$ grid. Two of them are shown below. On the right, an invalid assignment is shown: the distance between officers $$$2$$$ and $$$5$$$ changes from $$$1$$$ to $$$3$$$.
