#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

ll count_valid(ll N, ll A, ll B, ll C, ll D, ll d) {
    ll targetA = (d - B % d) % d;
    ll x, y;
    ll gA = exgcd(A, d, x, y);
    if (targetA % gA != 0) return 0;
    
    ll stepA = d / gA;
    x = (x % stepA + stepA) % stepA;
    ll mul = targetA / gA;
    ll X = (x * (mul % stepA)) % stepA;
    X = (X + stepA) % stepA;
    
    ll targetC = (d - D % d) % d;
    ll At = (C * stepA) % d;
    ll Bt = (targetC - (C * X) % d) % d;
    Bt = (Bt + d) % d;
    
    ll tx, ty;
    ll gt = exgcd(At, d, tx, ty);
    if (Bt % gt != 0) return 0;
    
    ll stepT = d / gt;
    tx = (tx % stepT + stepT) % stepT;
    ll mulT = Bt / gt;
    ll T = (tx * (mulT % stepT)) % stepT;
    T = (T + stepT) % stepT;
    
    ll M = stepT * stepA;
    ll startX = (X + T * stepA) % M;
    if (startX == 0) startX = M;
    
    if (startX > N) return 0;
    return (N - startX) / M + 1;
}

void solve() {
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    
    ll delta = abs(A * D - B * C);
    if (delta == 0) {
        ll g1 = __gcd(A, C);
        ll a = A / g1;
        ll k = B / a;
        
        ll sum_i = (N % MOD) * ((N + 1) % MOD) % MOD;
        sum_i = sum_i * 499122177 % MOD;
        ll ans = (g1 % MOD) * sum_i % MOD;
        ans = (ans + (k % MOD) * (N % MOD)) % MOD;
        cout << ans << "\n";
        return;
    }
    
    vector<ll> divs;
    for (ll i = 1; i * i <= delta; ++i) {
        if (delta % i == 0) {
            divs.push_back(i);
            if (i * i != delta) {
                divs.push_back(delta / i);
            }
        }
    }
    sort(divs.begin(), divs.end());
    
    int m = divs.size();
    vector<ll> exact(m, 0);
    for (int i = 0; i < m; ++i) {
        exact[i] = count_valid(N, A, B, C, D, divs[i]);
    }
    
    for (int i = m - 1; i >= 0; --i) {
        for (int j = i + 1; j < m; ++j) {
            if (divs[j] % divs[i] == 0) {
                exact[i] -= exact[j];
            }
        }
    }
    
    ll ans = 0;
    for (int i = 0; i < m; ++i) {
        ans = (ans + (exact[i] % MOD) * (divs[i] % MOD)) % MOD;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}