#include<bits/stdc++.h>
using namespace std;
int phi[100005],mu[100005],pr[100005];
bool p[100005];
int inv[100005];
const int mod=998244353;
int f[100005],*g[100005];
int tmp[2000005];
int h[100005][31][31];
int query(int n,int m){
    if(n>m)swap(n,m);
    int ans=0;
    for(int i=1;i<=m/30;i++){
        ans=(ans+1ll*f[i]*g[i][n/i]%mod*g[i][m/i]%mod)%mod;
    }//暴力
    int l=m/30+1;
    while(l<=n){
        int r=min(n/(n/l),m/(m/l));
        ans=(ans+h[r][n/l][m/l]-h[l-1][n/l][m/l])%mod;
        l=r+1;
    }//整除分块
    return (ans+mod)%mod;
}
int main(){
    int cnt=0;
    phi[1]=1;
    mu[1]=1;
    p[0]=p[1]=1;
    for(int i=2;i<=100000;i++){
        if(!p[i]){
            pr[++cnt]=i;
            mu[i]=-1;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*pr[j]<=100000;i++){
            p[i*pr[j]]=1;
            if(i%pr[j]!=0)phi[i*pr[j]]=phi[i]*(pr[j]-1);
            else {phi[i*pr[j]]=phi[i]*pr[j];break;}
            mu[i*pr[j]]=-mu[i];
        }
    }//求phi[i],mu[i]
    inv[1]=1;
    for(int i=2;i<=100000;i++)inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;//求逆元
    for(int i=1;i<=100000;i++){
        for(int j=1;i*j<=100000;j++){
            f[i*j]+=(1ll*inv[phi[i]]*mu[j]*i%mod+mod)%mod;
            if(f[i*j]>=mod)f[i*j]-=mod;
        }
    }
    int cur=0;
    for(int i=1;i<=100000;i++){
        g[i]=&tmp[cur];
        g[i][1]=phi[i];
        for(int j=2;i*j<=100000;j++){
            g[i][j]=g[i][j-1]+phi[i*j];
            if(g[i][j]>=mod)g[i][j]-=mod;
        }
        cur+=100000/i+1;
    }
    for(int i=1;i<=100000;i++){
        for(int j=1;j<=30;j++){
            for(int k=1;k<=30;k++){
                h[i][j][k]=(h[i-1][j][k]+1ll*f[i]*g[i][j]%mod*g[i][k]%mod)%mod;
            }
        }
    }//求h
    int t,x,y;cin>>t;
    while(t--){
        cin>>x>>y;
        cout<<query(x,y)<<'\n';
    }
    return 0;
}