题目描述

给出 $n,m$，求

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

一共有 $T$ 组数据。

输入格式

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

输出格式

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

样例

1
3 4

29

数据范围与提示

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