#include<bits/stdc++.h> //#define int long long #define int unsigned int #define endl "\n" #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) using namespace std; const int M=1<<30; int mu[200300],q; vector<int>P; map<int,int>fac[200300]; vector<int>d[200300]; int dct[200300],dct2[200300]; inline void init(){ memset(mu,-1,sizeof(mu)); mu[1]=1; for(int i=2;i<=2e5;i++){ if(fac[i].empty()) P.push_back(i),fac[i][i]++; for(int p:P){ if(p*i>2e5)break; fac[i*p]=fac[i]; fac[i*p][p]++; if(i%p==0){ mu[i*p]=0; break; } else mu[i*p]=-mu[i]; } } for(int i=1;i<=2e5;i++) for(int j=i;j<=2e5;j+=i) d[j].push_back(i); for(int i=1;i<=2e5;i++){ dct[i]=dct2[i]=1; for(pii e:fac[i]) dct[i]*=p2(e)+1, dct2[i]*=2*p2(e)+1; } } vector<int>S[200030]; vector<int>SS[21][21]; signed main(){ //freopen("math.in","r",stdin); //freopen("math.out","w",stdout); ios::sync_with_stdio(0); init(); for(int i=1;i<=2e5;i++) S[i].push_back(0); for(int i=1;i<=2e5;i++) for(int p:d[i]) S[p].push_back(S[p].back()+dct2[i]*dct[i/p]); for(int n=1;n<=20;n++) for(int m=1;m<=20;m++){ SS[n][m].push_back(0); for(int i=1;i*n<=4e5&&i*m<=4e5;i++) SS[n][m].push_back(SS[n][m].back()+mu[i]*S[i][n]*S[i][m]); } cin>>q; while(q--){ int n,m; cin>>n>>m; if(n>m)swap(n,m); int res=0; if(n<=5000) for(int i=1;i<=n;i++) res+=mu[i]*S[i][n/i]*S[i][m/i]; else{ for(int i=5000;i<=n;i++) res+=mu[i]*S[i][n/i]*S[i][m/i]; for(int l=5001,r;l<=n;l=r+1){ r=min(n/(n/l),m/(m/l)); res+=SS[n/l][m/l][r]-SS[n/l][m/l][l-1]; } } cout<<res%M<<endl; } cout.flush(); return 0; } /* */