seuOJ449 - 破晓狂想曲

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：2000 ms
空间限制：1024 MiB
题目标签：春季, 夏季, 2023

题目描述

Is this the real life? Is this just fantasy?

Caught in a landslide, no escape from reality

Open your eyes, look up to the skies and see

I'm just a poor boy, I need no sympathy

Because I'm easy come, easy go, little high, little low

Any way the wind blows doesn't really matter to me, to me

给定 $n,m$ ，求

\sum_{i=1}^n\sum_{j=1}^m\frac{\gcd(i,j)}{ij}\ mod\ 998244353

输入格式

第一行，一个数字 $t(1\le t \le 10^4)$ ，代表数据组数。

对于每组数据，两个整数 $n,m(1\le n,m \le10^6)$ 。

输出格式

对于每组数据，输出一行正整数代表答案。

可以证明答案一定可以表示成 $\frac{q}{p}$ ，其中 $q$ 为正整数， $p$ 为正整数，且存在一个正整数 $p^{(-1)}$ ，使得 $p^{(-1)}×p≡1\ mod\ 998244353$ ，即 $p$ 在模 $998244353$ 下一定存在逆元，你只需输出 $q×p^{(-1)}$ 模 $998244353$ 的值即可。

样例

输入样例：

5
1 3
22 13
1000 1000
114 5144
1000000 1000000

输出样例：

样例解释：
对于 $n=1,m=3$ ，结果为 $1+\frac{1}{2}+\frac{1}{3}=\frac{11}{6}$ ， $11·6^{-1}\ mod \ 998244353 = 831870296$ 。