Background

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!

Problem Description

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.

Input Format

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 Format

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

3
1 1
2 2
3 3

1
5
19

Hint

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