Description

毒瘤之神会问 $T$ 次，每次给定 $n, m$，Salamander 需要回答出 $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$。

Salamander 这么辣鸡当然不会做啦，于是把问题丢给了你。

Input Format

第一行包含一个正整数 $T$。

接下来 $T$ 行，每行包含两个正整数，用空格隔开，表示这次询问的 $n, m$。

Output Format

包含 $T$ 行，每行一个整数表示答案。

3
1 1
2 2
3 3

1
5
19

Hint

对于 $40\%$ 的数据，$T=1$，$n, m \le {10}^5$。
对于 $50\%$ 的数据，$T \le {10}^3$，$n, m \le {10}^5$。
对于另外 $10\%$ 的数据，$T \le {10}^4$，$n = m \le {10}^5$。
对于 $100\%$ 的数据，$1 \le T \le {10}^4$，$1 \le n, m \le {10}^5$。