Description
对于正整数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)。
Input
第一行一个数T，表示询问数。
接下来T行，每行两个数a,b，表示一个询问。
Output
对于每一个询问，输出一行一个非负整数作为回答。
Sample Input
4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957
Sample Output
35793453939901
14225956593420
4332838845846
15400094813
14225956593420
4332838845846
15400094813
HINT
【数据规模】
T<=10000
1<=a,b<=10^7
这道题是可以用莫比乌斯反演，下面是程序：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=1e7+5;
bool z[N];
int p[N],g[N],mn[N],a[N],l;
void work(){int i,j,tp;for(i=2;i<=1e7;i++){if(!z[i]){a[i]=p[++l]=i;mn[i]=g[i]=1;}for(j=1;(tp=i*p[j])<=1e7&&j<=l;j++){z[tp]=1;if(!(i%p[j])){mn[tp]=mn[i]+1;a[tp]=a[i]*p[j];if(i==a[i]){g[tp]=1;}else{g[tp]=(mn[tp]==mn[i/a[i]]?-g[i/a[i]]:0);}break;}mn[tp]=1;a[tp]=p[j];g[tp]=(mn[i]==1?-g[i]:0);}}for(i=1;i<=1e7;i++){g[i]+=g[i-1];}
}
long long f(int a,int b){int i,last;long long s=0;if(a>b){swap(a,b);}for(i=1;i<=a;i=last+1){last=min(a/(a/i),b/(b/i));s+=(long long)(g[last]-g[i-1])*(a/i)*(b/i);}return s;
}
int main(){work();int t,a,b;scanf("%d",&t);while(t--){scanf("%d%d",&a,&b);printf("%lld\n",f(a,b));}return 0;
}
