#include<bits/stdc++.h> #pragma gcc optimize(3) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define x1 x114514 #define y1 y114514 #define p_b push_back #define m_p make_pair #define uint unsigned int using namespace std; typedef long long ll; const int maxn=2e5+10,mod=1073741824; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,miu[maxn],pr[maxn],ct,b[maxn],bel[maxn]; uint f[maxn],g[maxn],ret[maxn]; vector<pi>P[maxn]; vector<uint>S[maxn]; vector<int>Q[maxn]; uint res[maxn]; struct node { int n,m,id; }dd[maxn]; bool operator<(node a,node b){ if(bel[a.n]!=bel[b.n])return bel[a.n]<bel[b.n]; return a.m<b.m; } uint d(int x){ uint res=1; for(auto it:P[x])res=res*(it.p2*2+1); return res; } uint d2(int x){ uint res=1; for(auto it:P[x])res=res*(it.p2+1); return res; } void init(){ up(i,1,2e5){ int x=i; for(int j=2;j*j<=x;++j){ if(x%j==0){ int ct=0; while(x%j==0)x/=j,ct++; P[i].p_b(m_p(j,ct)); } }if(x!=1)P[i].p_b(m_p(x,1)); }miu[1]=1; up(i,2,2e5){ if(!b[i])pr[++ct]=i,miu[i]=-1; up(j,1,ct){ if(i*pr[j]>2e5)break; b[i*pr[j]]=1; miu[i*pr[j]]=-miu[i]; if(!(i%pr[j])){miu[i*pr[j]]=0;break;} } }S[0].resize(2e5+5); up(i,1,2e5){ S[i].resize(2e5/i+5); up(j,1,2e5/i)S[i][j]=S[i-1][j]+d(i*j)*d2(i); } up(i,1,2e5){ up(j,1,2e5/i)Q[i*j].p_b(i); } int len=sqrt(2e5); up(i,1,2e5)bel[i]=(i-1)/len+1; } uint calc(int n,int m){ uint res=0; for(int x:Q[n])if(x!=n)res+=miu[x]*(S[n/x][x]-S[n/x-1][x])*S[m/x][x]; res+=miu[n]*S[1][n]*S[m/n][n]; return res; } void slv(){ int q=read(); up(i,1,q)dd[i].n=read(),dd[i].m=read(),dd[i].id=i; sort(dd+1,dd+q+1); int n=1,m=1;uint res=1; up(i,1,q){ while(n<dd[i].n)res+=calc(++n,m); while(m<dd[i].m)res+=calc(++m,n); while(n>dd[i].n)res-=calc(n--,m); while(m>dd[i].m)res-=calc(m--,n); ret[dd[i].id]=res; }up(i,1,q)printf("%u\n",ret[i]%mod); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; }int main(){ // freopen("math.in","r",stdin); // freopen("math.out","w",stdout); init();slv(); fclose(stdin); fclose(stdout); return 0; }