题目链接：https://cn.vjudge.net/problem/HYSBZ-3309
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn =1e7+5;
const int mod=1e9+7;
///筛法筛数的最大质数幂，素数，miu函数
/*
按正常的套路最后都能得到这个式子，
sigma a/i*b/i* f*miu(i),i=1~i;
问题的关键是这个式子的后缀如何处置，
下面就开始分析这个函数的性质，姑且命名这个函数为g,
首先如果x的质数次幂为a1,a2,...ak，
如果他们不一样会有什么结果？首先很容易想到如果最高次幂比次高次幂多2或是更多，答案为零，
因为这时候f函数已经是个常数，
如果多1，这时候答案分两种，a和a-1,如果要取到a,
对函数的贡献也为零，因为次幂为a的miu函数都不能取，
如果取到a-1,则在次幂为a 的质数集合中至少取一个，
对每个进行枚举，答案还是零，有点组合的思想在里面，因为对每个质因子，
其余的选择数都是一个常数。那么至此我们可以看到，当质次幂错落时答案都是零，
如果次幂都为a呢，答案还是分为两种，a,a-1。
g(T)=a(对符合条件的质数进行组合取法)+(a-1)*miu(p1*p2*...pk)，
我们知道a(对所有质数数进行组合取)=0，
所以这种情况答案为-1*miu(p1*p2*...pk)。下面就是如何线性筛这玩意儿了，
DP记录两个玩意儿，
x的最小质数的次幂，除去最小质数后的余数。
这样DP过程就可以描述了，
在遇到其最小质因子时候，
更新上面两个描述的变量，
用这两个东西来推g函数，
详见代码吧，感觉筛法思想跟DP思想很接近，
状态的坍塌利用最小质因子来找规律。*/
int prim[maxn/10],tot=0;
int vis[maxn],miu[maxn];
int rst[maxn];///除去最小质因子数后的数
int np[maxn];///最小质因子的幂数
ll g[maxn];///答案函数
void sieve()
{miu[1]=1;for(int i=2;i<maxn;i++){if(vis[i]==0){prim[tot++]=i;miu[i]=-1;np[i]=g[i]=rst[i]=1;}for(int j=0;j<tot;j++){if(1LL*i*prim[j]>=maxn) break;int k=i*prim[j]; vis[k]=1;if(i%prim[j]){miu[k]=-miu[i];np[k]=1,rst[k]=i;g[k]=(np[i]==1?-g[i]:0);}else{np[k]=np[i]+1,rst[k]=rst[i];if(rst[i]==1) g[k]=1;///???else g[k]=(np[k]==np[rst[k]]?-g[rst[k]]:0);break;}}}for(int i=1;i<maxn;i++) g[i]+=g[i-1];
}
int a,b;
ll ret;
int main()
{sieve();int t;scanf("%d",&t);while(t--){scanf("%d%d",&a,&b);if(a>b) swap(a,b);ret=0;for(int i=1,j;i<=a;i=j+1){j=min(a/(a/i),b/(b/i));ret+=1LL*(a/i)*(b/i)*(g[j]-g[i-1]);}printf("%lld\n",ret);}return 0;
}