P4240 Trial of the God of "Duliu"

At Salamander's doorstep lies a long road. As spring approaches again, Salamander discovers a row of "duliu" growing by the roadside! Salamander wants to take some "duliu" home, but then a God of "Duliu" pops out from among them! God of "Duliu": Do you want to take the "duliu"? If you want to take them, you must answer my question! If you can't answer it, you'd better go home!

The God of "Duliu" will ask $T$ times. Each time, given $n, m$, Salamander must answer $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$. Salamander cannot solve it, so he passes the problem to you.

The first line contains a positive integer $T$. Then follow $T$ lines; each line contains two positive integers separated by a space, representing this query's $n, m$.

Output $T$ lines, each containing one integer representing the answer.

For $40\%$ of the testdata, $T = 1$, $n, m \le 10^5$. For $50\%$ of the testdata, $T \le 10^3$, $n, m \le 10^5$. For another $10\%$ of the testdata, $T \le 10^4$, $n = m \le 10^5$. For $100\%$ of the testdata, $1 \le T \le 10^4$, $1 \le n, m \le 10^5$. Translated by ChatGPT 5