25648번 - The Pool 다국어

Marisa wants to build an $n \times m$ rectangular swimming pool for Alice. To do this, Marisa can select four integer points on an infinite two-dimensional grid, and cast magic. For example, the following picture shows three possible ways to build a $5 \times 5$ swimming pool.

Marisa soon learns that there are many ways to build the pool since four sides of the pool can be non-parallel to coordinate axes. Here two ways are considered different if and only if the pool in one way can't be translated (moved without rotation and flipping) to the pool in the other way. Now Marisa becomes curious about the total number of $1 \times 1$ squares completely inside the pool for all possible ways. As the result can be very large, you should print it modulo $998\,244\,353$.

The first line contains one integer $T$ ($1\leq T\leq 10^4$) denoting the number of test cases.

Each test case is given on a single line containing two integers $n$ and $m$ ($1 \leq n, m \leq 10^{18}$) denoting the size of swimming pool.

It is guaranteed that there are at most 10 cases where $\max(n, m) > 10^9$.

For each test case, print one number, denoting the total number of $1 \times 1$ squares completely inside the pool for all possible ways (modulo $998\,244\,353$).

As shown in the picture, there are exactly three different ways to build the pool. The corresponding numbers of $1 \times 1$ squares completely inside the pool in these three ways are $25$, $13$, and $13$. So the total number is $51$.