题目背景

Salamander 的家门口是一条长长的公路。

又是一年春天将至，Salamander 发现路边长出了一排毒瘤！

Salamander 想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！

毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！

题目描述

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

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

输入格式

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

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

输出格式

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

3
1 1
2 2
3 3

1
5
19

提示

对于 $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$。