#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

template <u32 Mod> class ModInt {
    using Self = ModInt<Mod>;
    static_assert(Mod <= std::numeric_limits<i32>::max());
public:
    ModInt(i64 value = 0) {
        if (value < 0) {
            value_ = (Mod - (-value % Mod)) % Mod;
        } else {
            value_ = value % Mod;
        }
    }

    ModInt(const Self& other) : value_(other.value_) {}

    operator i32() const {
        return value_;
    }

    operator i64() const {
        return value_;
    }

    Self operator+(const Self& other) const {
        Self res(*this);
        res += other;
        return res;
    }

    Self operator-(const Self& other) const {
        Self res(*this);
        res -= other;
        return res;
    }

    Self operator*(const Self& other) const {
        Self res(*this);
        res *= other;
        return res;
    }

    Self operator/(const Self& other) const {
        Self res(*this);
        res /= other;
        return res;
    }

    Self operator-() const {
        Self res(0);
        res -= *this;
        return res;
    }

    Self pow(i64 power) const {
        Self ret(1), p(*this);
        if (power < 0) {
            power *= -1;
            p = p.inv();
        }
        for (i64 i = 0; (1 << i) <= power; ++i) {
            if ((power >> i) & 1) ret *= p;
            p *= p;
        }
        return ret;
    }

    Self& operator+=(const Self& other) {
        value_ += other.value_;
        if (value_ >= Mod) value_ -= Mod;
        return *this;
    }

    Self& operator-=(const Self& other) {
        value_ += Mod - other.value_;
        if (value_ >= Mod) value_ -= Mod;
        return *this;
    }

    Self& operator*=(const Self& other) {
        value_ = (u32)(((u64)value_ * other.value_) % Mod);
        return *this;
    }

    Self& operator/=(const Self& other) {
        *this *= other.inv();
        return *this;
    }

    Self inv() const {
        if (value_ < inv_tbl_.size()) return inv_tbl_[value_];
		if (Mod - value_ < inv_tbl_.size()) return Mod - inv_tbl_[Mod - value_];
        else return pow(Mod - 2);
    }

private:
    u32 value_;
    static const std::vector<Self> inv_tbl_;
};

template <u32 Mod>
std::vector<ModInt<Mod>> create_inv_tbl_(u32 n) {
    std::vector<ModInt<Mod>> res;
    res.reserve(n + 1);
    res.push_back(0);
    res.push_back(1);
    for (u32 i = 2; i <= n; ++i) {
        // MOD / i == 0
        // MOD // i + (MOD % i) / i == 0
        // 1 / i == -(MOD // i) / (MOD % i)
        res.push_back(res[Mod % i] * ModInt<Mod>(Mod - (Mod / i)));
    }
    return res;
}

template <u32 Mod>
const std::vector<ModInt<Mod>> ModInt<Mod>::inv_tbl_ = create_inv_tbl_<Mod>(1000000);

template <class T, u32 Mod>
ModInt<Mod> operator+(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) + y;
}

template <class T, u32 Mod>
ModInt<Mod> operator-(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) - y;
}

template <class T, u32 Mod>
ModInt<Mod> operator*(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) * y;
}

template <class T, u32 Mod>
ModInt<Mod> operator/(T x, ModInt<Mod> y) {
    return ModInt<Mod>(x) / y;
}

template <class T, u32 Mod>
ModInt<Mod> operator+(ModInt<Mod> x, T y) {
    return x + ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator-(ModInt<Mod> x, T y) {
    return x - ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator*(ModInt<Mod> x, T y) {
    return x * ModInt<Mod>(y);
}

template <class T, u32 Mod>
ModInt<Mod> operator/(ModInt<Mod> x, T y) {
    return x / ModInt<Mod>(y);
}

typedef ModInt<MOD> mint;

int T;
int H, W;

mint fact[101010], facti[101010];

mint C(int x, int y) {
    if (0 <= y && y <= x) {
        return fact[x] * facti[x - y] * facti[y];
    } else {
        return 0;
    }
}

int mygcd(int x, int y) {
    while (y) {
        int tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

mint solve(int H, int W) {
    mint ans = 0;
    ans += mint(H) * mint(W);

    if (H % 4 == 0 && W % 4 == 0) {
        ans += 16;
    }

    int g = mygcd(H, W);
    if (g >= 4) {
        ans += 2 * g;
    }

    if (g >= 5 && (H % 3 == 0 || W % 3 == 0)) {
        ans += g * 12;
    }

    /*
    if (g % 2 == 0) {
        int g2 = g / 2;
        mint tmp = 0;

        for (int n5 = 1; n5 <= g2 / 5; ++n5) {
            if ((g2 - 5 * n5) % 3 != 0) continue;
            int n3 = (g2 - 5 * n5) / 3;
            // printf("%d %d\n", n5, n3);
            if (n5 >= 1) tmp += C(n5 - 1 + n3, n5 - 1) * 5;
            if (n3 >= 1) tmp += C(n5 + n3 - 1, n3 - 1) * 3;
        }
        // printf("%d\n", (int)tmp);
        ans += tmp * tmp * 4;
    }
    */
    if (g % 2 == 0) {
        int g2 = g / 2;

        mint tmp[2] = {0, 0};
        for (int n5 = 1; n5 <= g2 / 5; ++n5) {
            if ((g2 - 5 * n5) % 3 != 0) continue;
            int n3 = (g2 - 5 * n5) / 3;
            // printf("%d %d\n", n5, n3);
            if (n5 >= 1) tmp[n5 % 2] += C(n5 - 1 + n3, n5 - 1) * 5;
            if (n3 >= 1) tmp[n5 % 2] += C(n5 + n3 - 1, n3 - 1) * 3;
        }
        ans += tmp[0] * tmp[0] * 4;
        ans += tmp[1] * tmp[1] * 4;
        // printf("%d\n", (int)tmp);
    }
    return ans;
}

int main()
{
    fact[0] = facti[0] = 1;
    for (int i = 1; i < 101010; ++i) {
        fact[i] = fact[i - 1] * i;
        facti[i] = facti[i - 1] / i;
    }

    scanf("%d", &T);
    for (;T--;) {
        scanf("%d%d", &H, &W);

        mint ans = solve(H, W);
        printf("%d\n", (int)ans);
    }
	return 0;
}