#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int iu=1e5;
ll gcd(ll x,ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
ll f[100001],g[100001];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	f[2]=mod-3;f[4]=mod-5;
	g[2]=mod-3;g[4]=5;
	for(int i=0; i<=iu ;i++){
		if(i>=5) f[i]+=f[i-5],g[i]-=g[i-5];
		if(i>=3) f[i]+=f[i-3],g[i]+=g[i-3];
		f[i]%=mod;f[i]+=mod;f[i]%=mod;
		g[i]%=mod;g[i]+=mod;g[i]%=mod;
	}
	for(int i=0; i<=iu ;i++){
		if(i%3==2){
			f[i]=(f[i]+3)%mod;
			g[i]=(g[i]+3)%mod;
		}
	}
	for(int i=iu; i>=1 ;i--){
		f[i]=f[i-1]*pw(i,mod-2)%mod;
		g[i]=g[i-1]*pw(i,mod-2)%mod;
	}
	for(int i=1; i<=iu ;i++){
		ll u=f[i],v=g[i];
		f[i]=(2*mod-u-v)*((mod+1)/2)%mod;
		g[i]=(mod+v-u)*((mod+1)/2)%mod;
	}
	int t;cin >> t;
	while(t--){
		ll n,m;cin >> n >> m;
		ll h=gcd(n,m);
		ll ans=0;
		if(h%2==0){
			ll w=h/2;
			ans=(f[w]*f[w]+g[w]*g[w])%mod;
			ans=ans*n%mod;
			ans=ans*m%mod;
		}
		if(h>=4) ans=(ans+2*h)%mod;
		if(h%6==0) ans=(ans+36)%mod;
		if(n%4==0 && m%4==0) ans=(ans+16)%mod;
		ans=(ans+n*m)%mod;
		cout << ans << endl;
	}
}