A. 破晓狂想曲
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定$$$n,m$$$，求 $$$$$$ \sum_{i=1}^n\sum_{j=1}^m\frac{\gcd(i,j)}{ij}\ mod\ 998244353 $$$$$$

Input

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

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

Output

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

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

Example
Input
5
1 3
22 13
1000 1000
114 5144
1000000 1000000
Output
831870296
840003385
865445419
863853786
434780206
Note

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