#include <cstdio>
#define int long long

const int mod = 998244353;
inline int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}
bool mark[10000005];
int pri[1000005], phi[10000005], pow2[10000005], facs[100005], cnt;
void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++ i) {
        if (!mark[i]) phi[i] = i - 1, pri[++ cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++ j) {
            mark[i * pri[j]] = true;
            if (i % pri[j] == 0) {phi[i * pri[j]] = phi[i] * pri[j]; break;}
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
}
    }
int gcd(int n, int m) {return m ? gcd(m, n % m) : n;}
int F(int m, int a, int b) {
    if (!a || !b) return 0;
    int g = gcd(a, b), s = 1;
    while (g --) s *= m;
    return s + 1;
}

signed main() {
    init(10000000);
    pow2[0] = 1;
    for (int i = 1; i <= 10000000; ++ i) pow2[i] = 2ll * pow2[i - 1] % mod;
    int _; scanf("%lld", &_);
    while (_ --) {
        int m, A, B, C, D; scanf("%lld%lld%lld%lld%lld", &m, &A, &B, &C, &D);
        int n = (F(m, C, D) - F(m, A, B)) / m, ans = 0, len = 2;
        facs[1] = 1, facs[2] = m;
        for (int i = 1; pri[i] * pri[i] <= m && pri[i] < m; ++ i) if (m % pri[i] == 0) {
            facs[++ len] = pri[i];
            if (pri[i] * pri[i] != m) facs[++ len] = m / pri[i];
        }
        for (int i = 1; i <= len; ++ i) {
            int g = facs[i];
            if ((m / g) & 1)
                ans = (ans + 1ll * phi[m / g] * qpow(2, n % (mod - 1) * g % (mod - 1))) % mod;
        }
        ans = 1ll * ans * qpow(m, mod - 2) % mod;
        printf("%lld", ans);
    }
    return 0;
}