#230 Good Triangles

Statement

Statement language

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$ .

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$ .

Input

The input is given in the following format.

$T$ $N_1\ M_1$ $N_2\ M_2$

Output

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

Constraints

$1 \leq T \leq 1\ 000\ 000$ .
$1 \leq N_i \leq 1000$ ().

Subtasks

#	Score	Constraints
1	100	There are no additional constraints.

Samples

Input

Output

0
2
8

In a $2 \times 2$ grid, it is impossible to choose three points of the same color.

There are $2$ good triangles in a $2 \times 3$ grid, and $8$ good triangles in a grid.