题目描述

给出 $n,m$，求

$$\sum{i=1}^n\sum{j=1}^m\varphi(ij)\pmod{998244353}$$

一共有 $T$ 组数据。

输入格式

第一行包含一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行包含两个正整数 $n, m$。

输出格式

输出 $T$ 行，每行一个正整数。

样例

input

1
3 4

output

29

数据范围与提示

对于 $ 40\% $ 的数据，$ T=1 $；
对于 $ 50\% $ 的数据，$ 1\leq T\leq 1000$；
对于另 $ 10\% $ 的数据，$ n = m $；
对于 $ 100\% $ 的数据，$ 1\leq T,n,m\leq 10^5 $。