#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ; 
using i128 = __int128; 
using f64 = long double;

cs int Mod = 998244353; 
int T; 
ll p;
f64 invp;
void setmod(ll x) {
	p = x, invp = (f64) 1 / x;
}
ll mul(ll a, ll b) {
	ll z = a * invp * b + 0.5;
	ll res = a * b - z * p;
	return res + (res >> 63 & p);
}
ll pow(ll a, ll x, ll res = 1) {
	for(;x;x >>= 1, a = mul(a, a))
		if(x & 1) res = mul(res, a);
	return res;
}
bool checkprime(ll p) {
	if(p == 1) return 0;
	setmod(p);
	ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
	for(ll a : {2, 3, 5, 7, 11, 13, 82, 373}) {
		if(a % p == 0)
			continue;
		ll x = pow(a, s), y;
		for(int i = 0;i < d;++i, x = y) {
			y = mul(x, x);
			if(y == 1 && x != 1 && x != p - 1)
				return 0;
		}
		if(x != 1) return 0;
	}
	return 1;
}

ll rho(ll n) {
	if(!(n & 1)) return 2;
	static std::mt19937_64 gen((size_t)"hehezhou");
	ll c = gen() % (n - 1) + 1, y = gen() % (n - 1) + 1;
	auto f = [&](ll o) {
		o = mul(o, o) + c;
		return o >= n ? o - n : o;
	};
	setmod(p);
	for(int l = 1;;l <<= 1) {
		ll x = y, g = 1;
		for(int i = 0;i < l;++i) y = f(y);
		const int d = 512;
		for(int i = 0;i < l;i += d) {
			ll sy = y;
			for(int j = 0;j < std::min(d, l - i);++j) {
				y = f(y), g = mul(g, (y - x + n));
			}
			g = std::__gcd(n, g);
			if(g == 1)
				continue;
			if(g == n)
				for(g = 1, y = sy;g == 1;)
					y = f(y), g = std::__gcd(n, y - x + n);
			return g;
		}
	}
}
std::vector<ll> factor(ll x) {
	std::queue<ll> q; q.push(x);
	std::vector<ll> res;
	for(;q.size();) {
		ll x = q.front(); q.pop();
		if(x == 1) continue;
		if(checkprime(x)) {
			res.push_back(x);
			continue;
		}
		ll y = rho(x);
		q.push(y), q.push(x / y);
	}
	sort(res.begin(), res.end());
	return res;
}
struct cp {
    ll x, y;
    cp(ll x = 0, ll y = 0) : x(x), y(y) {}
    cp operator + (cs cp &b) { return cp(x + b.x, y + b.y); }
    cp operator - (cs cp &b) { return cp(x - b.x, y - b.y); }
    cp operator * (cs cp &b) { return cp(x * b.x - y * b.y, x * b.y + y * b.x); }
    cp conj() { return cp(x, -y); }
    i128 norm() { return x * x + y * y; }
}; 
mt19937_64 rnd(223);
ll R(f64 x) { return round(x); }
cp operator / (cs cp & a, cs cp & b) {
	complex <f64> A(a.x, a.y), B(b.x, b.y), C = A / B; 
	// cout << C.real() << ' ' << C.imag() << endl;
    return cp(R(C.real()), R(C.imag()));
}
cp mod(cp a, cp b) {
    cp c = a / b; 
    return a - b * c; 
}
cp gcd(cp a, cp b) {
    if(b.norm() == 0) return a; 
    cp c = mod(a, b);
	// cout << (ll) a.norm() << ' ' << (ll)  b.norm() << ' ' << (ll)  c.norm() << ' ' << a.x << ' ' << a.y << ' ' << b.x << ' ' <<b.y << ' ' << c.x << ' ' << c.y << endl;
    
	assert(c.norm() < b.norm());
	return gcd(b, c);
}
ll ksm(ll a, ll b, ll p) {
	ll c = 1; 
	for(; b; b >>= 1, a = (i128) a * a % p)
		if(b & 1) c = (i128) c * a % p;
	return c; 
}
cp get(ll p) {
    cp c(1, 0);
    while(1) {
        ll x = rnd() % p;
        ll y = ksm(x, (p - 1) / 4, p);
        if(((i128) y * y + 1) % p == 0) {
			c = cp(y, 1); break;
		}
    }
    c = gcd(c, cp(p, 0));
	return c; 
}
ll calc(ll x, ll y, ll n, ll m) {
	ll d = __gcd(x, y);
	if((i128) d * m % n) return 0; 
	i128 all = (x + (i128) y * m / n) * (y + (i128) x * m / n); 
	// cout << (ll) all << endl;
	all -= ((i128) x * m / n - y) * ((i128) y * m / n - x);
	// cout << (ll) all << endl;
	assert(all % 2 == 0);
	i128 e = x + y - d; 
	// cout << (ll) e << endl;
	e = e + (i128) e * m / n; 
	all = all / 2 - e; 
	// cout << x << ' ' << y << ' ' << n<< ' ' << m << ' ' << (ll)all % Mod << endl;
	return all % Mod;
}
void Main() {
    ll n, m; 
    cin >> n >> m; 
    if(n > m) swap(n, m);
    vector <ll> pr = factor (n);
    map <ll, int> mp;
    for(ll x : pr) ++ mp[x];
    vector <cp> ans = {{1, 0}, {0, 1}}; 
    for(auto [x, y] : mp) {
		// cout << x << ' ' << y << endl;
        if(x % 4 == 1) {
            cp ab = get(x), ba = ab.conj(); 
            vector <cp> nxt; 
            for(int i = 0; i <= y; i++) {
                cp cur(1, 0);
                for(int j = 0; j < i; j++) 
                    cur = cur * ab; 
                for(int j = i; j < y * 2; j++)
                    cur = cur * ba;
				// cout << "FFFFGGGG " << cur.x << ' ' << cur.y << endl;
                for(auto c : ans) 
                    nxt.pb(c * cur);
            }
			swap(nxt, ans);
        } else {
            for(int t = 0; t < y; t++)
                for(auto & c : ans)
                    c = c * x; 
        }
    }
	ll sum = (i128) n * m % Mod;  
    for(auto c : ans) {
        ll x = c.x, y = c.y;
        x = abs(x), y = abs(y);
		// cout << "Case " << x << ' ' << y << endl;
		if(x && y) sum = (sum + calc(x, y, n, m)) % Mod; 
    }
	if(n != m) sum = sum * 2 % Mod; 
	static int tt = 0; 
	if(++ tt == 6465) cout << n << ' ' << m << endl;
	if(T <= 10) cout << sum << '\n';
}
int main() {
	#ifdef zqj
	freopen("1.in", "r", stdin);
	#endif
    cin >> T; 
    while(T--) Main();
    return 0;
}