#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;
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
int T;
cin >> T;
while(T--) Main();
return 0;
}