Good Triangles

Consider all lattice points $(x,y)$ in an $N \times M$ grid, where $1 \leq x \leq N$ and $1 \leq y \leq M$.

A lattice point $(x,y)$ is black if $(x+y) \bmod 2 = 0$, and white if $(x+y) \bmod 2 = 1$.

Choose three distinct points $A,B,C$. If the three points are collinear, they do not form a triangle and are not counted.

Let $W$ be the area of the parallelogram formed by the vector from $A$ to $B$ and the vector from $A$ to $C$.

If the three points all have the same color and $W$ is prime, then these three points are called a good triangle.

For given $N,M$, find the number of good triangles. A triangle is considered as a set of three points, so choices that differ only by the order of the same three points are counted once.

Print the answer modulo $998244353$.

The input is given in the following format.

$T$ $N_1\ M_1$ $N_2\ M_2$ $\vdots$ $N_T\ M_T$

$T$ is the number of test cases.

For each test case, print the number of good triangles modulo $998244353$ on a separate line.

• $1 \leq T \leq 1\ 000\ 000$.
• $1 \leq N_i \leq 1000$ ($1 \leq i \leq T$).
• $1 \leq M_i \leq 1000$ ($1 \leq i \leq T$).
• $\sum_{i=1}^{T} N_iM_i \leq 10^6$.