#P17790. 毒瘤之神的考验

毒瘤之神的考验

P4240 毒瘤之神的考验

题目描述

询问问 TT 次,每次给定 n,mn, m,请回答出 $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$。

输入格式

第一行包含一个正整数 TT。

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

输出格式

包含 TT 行,每行一个整数表示答案。

输入输出样例 #1

输入 #1

3
1 1
2 2
3 3

输出 #1

1
5
19

说明/提示

对于 40%40\% 的数据,T=1T=1,n,m≤105n, m \le {10}^5。
对于 50%50\% 的数据,T≤103T \le {10}^3,n,m≤105n, m \le {10}^5。
对于另外 10%10\% 的数据,T≤104T \le {10}^4,n=m≤105n = m \le {10}^5。
对于 100%100\% 的数据,1≤T≤1041 \le T \le {10}^4,1≤n,m≤1051 \le n, m \le {10}^5。