Description:


对于正整数 \(n\) ,定义 \(f(n)\)\(n\) 所含质因子的最大幂指数。
例如 \(f(1960)=f(2^3\times 5^1\times 7^2)=3\) , \(f(10007)=1\) , \(f(1)=0\)
给定正整数 \(a,b\) ,求

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

Input:


第一行一个数 \(T\) ,表示询问数。
接下来 \(T\) 行,每行两个数 \(a,b\) ,表示一个询问。

Output:


对于每一个询问,输出一行一个非负整数作为回答。

Sample Input:


Sample Output:


HINT:

数据范围:
\(T\le 10000,1\le a,b\le 10^7\)

题解:


这个题变换相对而言还比较简单,但是发现筛的方法有难度。

不妨设 \(n\le m\)

\(g(x) = \sum_{d|x} f(d) \mu (\frac{x}{d})\)

\(g\) 函数打一张表。
然后就会发现规律了:

\(x=\prod_{i=1}^k p_i^c\) ,则 \(g(x) = (-1)^{k+1}\) 。否则 \(g(x)=0\)

其实是有证明的,但是我不会。

然后就分个块没有了。