1379: 数论大亡

\[ \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)^{\varphi(\sum_{d \mid \gcd(i, j)}\varphi(d))} \]

$\varphi(x)$ 表示小于 $x$ 的正整数中与 $x$ 互质的数的个数，$\varphi(1)=1$，$\gcd(x,y)$表示 $x$ 和 $y$ 最大公因子。

此时 $Fatefly$ 想出来一个美妙的解法，故而他决定吃 一顿 KFC 奖励自己。但不幸的是，他忘记把解法写下来了，请让你帮其计算。

由于结果可能非常大，请输出结果对 \(998\,244\,353\) 取模后的值。

第一行包含一个整数 \(T\) (\(1 \le T \le 10^4\))，表示测试数据的组数。

接下来的 \(T\) 行，每行包含两个正整数 \(n\) 和 \(m\) (\(1 \le n, m \le 10^6\))。

对于每次启动，输出一行一个整数，表示答案。

2
3 3
5 7

18
695