对于正整数n，定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
给定正整数a,b，求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。

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

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

【数据规模】

T<=10000

1<=a,b<=10^7

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cmath> 6 #include<cstring> 7 #define LL long long 8 using namespace std; 9 const int mxn=10000010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 int pri[mxn],cnt;17 int mu[mxn],last[mxn],w[mxn],g[mxn];18 bool vis[mxn];19 LL smm[mxn];20 void init(){21     mu[1]=1;22     for(int i=2;i<mxn;i++){23         if(!vis[i]){24             pri[++cnt]=i;last[i]=1;w[i]=1;25             mu[i]=-1;g[i]=1;26         }27         for(int j=1;j<=cnt && pri[j]*i<mxn;j++){28             int tmp=pri[j]*i;29             vis[tmp]=1;30             if(i%pri[j]==0){31                 last[tmp]=last[i];32                 w[tmp]=w[i]+1;33                 mu[tmp]=0;34                 if(last[tmp]==1) g[tmp]=1;35                 else    if(w[last[tmp]]==w[tmp])g[tmp]=-g[last[tmp]];36                         else g[tmp]=0;37                 break;38             }39             last[tmp]=i;40             mu[tmp]=-mu[i];41             w[tmp]=1;42             g[tmp]=(w[i]==1)?(-g[i]):0;43         }44     }45     for(int i=1;i<mxn;i++)smm[i]=smm[i-1]+g[i];46     return;47 }48 int a,b;49 void solve(){50     if(a>b)swap(a,b);51     LL ans=0;52     for(int i=1,pos;i<=a;i=pos+1){53         pos=min(a/(a/i),b/(b/i));54         ans+=(smm[pos]-smm[i-1])*(LL)(a/i)*(b/i);55     }56     printf("%lld\n",ans);57     return;58 }59 int main(){60 //    freopen("in.txt","r",stdin);61     init();62     int T=read();63     while(T--){64         a=read();b=read();65         solve();66     }67     return 0;68 }