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