#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=4e6+50;
const int Mod=998244353;
vector<int> prim;
bool mark[N];
int mo[N];
ll Mo[N];
unordered_map<ll,ll> MO;
void Sieve() {
    mo[1]=1;
    FOR(i,2,N-1) {
        if(!mark[i]) {
            prim.push_back(i);
            mo[i]=-1;
        }
        for(auto p: prim) {
            int x=i*p;
            if(x>=N) break;
            mark[x]=1;
            if(i%p==0) break;
            else mo[x]=-mo[i];
        }
    }
    FOR(i,1,N-1) Mo[i]=Mo[i-1]+mo[i];
}
ll sum_mo(ll n) {
    if(n<N) return Mo[n];
    if(MO.count(n)) return MO[n];
    ll t=1;
    for(ll i=2,j; i<=n; i=j+1) {
        j=n/(n/i);
        t-=(j-i+1)*sum_mo(n/i);
    }
    return MO[n]=t;
}
ll g(ll n,ll a,ll b,ll m) {
    if(b==0) return n%Mod*(a/m)%Mod;
    if(a>=m) return (n%Mod*(a/m)+g(n,a%m,b,m))%Mod;
    if(b>=m) {
        if(n&1) return ((n-1)/2%Mod*(n%Mod)%Mod*(b/m)+g(n,a,b%m,m))%Mod;
        else return (n/2%Mod*((n-1)%Mod)%Mod*(b/m)+g(n,a,b%m,m))%Mod;
    }
    return g((a+b*n)/m,(a+b*n)%m,m,b);
}
ll a,b,c,d;
ll f(ll n) {
    return g(n,c,c,d)-g(n,a-1,a,b);
}
void solve() {
    ll n;
    cin >> n >> a >> b >> c >> d;
    ll res=0;
    for(ll l=1,r; l<=n; l=r+1) {
        r=n/(n/l);
        res=(res+(f(n/l)%Mod)*((sum_mo(r)-sum_mo(l-1))%Mod))%Mod;
    }
    if(res<0) res+=Mod;
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Sieve();
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=4e6+50;
const int Mod=998244353;
vector<int> prim;
bool mark[N];
int mo[N];
ll Mo[N];
unordered_map<ll,ll> MO;
void Sieve() {
    mo[1]=1;
    FOR(i,2,N-1) {
        if(!mark[i]) {
            prim.push_back(i);
            mo[i]=-1;
        }
        for(auto p: prim) {
            int x=i*p;
            if(x>=N) break;
            mark[x]=1;
            if(i%p==0) break;
            else mo[x]=-mo[i];
        }
    }
    FOR(i,1,N-1) Mo[i]=Mo[i-1]+mo[i];
}
ll sum_mo(ll n) {
    if(n<N) return Mo[n];
    if(MO.count(n)) return MO[n];
    ll t=1;
    for(ll i=2,j; i<=n; i=j+1) {
        j=n/(n/i);
        t-=(j-i+1)*sum_mo(n/i);
    }
    return MO[n]=t;
}
ll g(ll n,ll a,ll b,ll m) {
    if(b==0) return n%Mod*(a/m)%Mod;
    if(a>=m) return (n%Mod*(a/m)+g(n,a%m,b,m))%Mod;
    if(b>=m) {
        if(n&1) return ((n-1)/2%Mod*(n%Mod)%Mod*(b/m)+g(n,a,b%m,m))%Mod;
        else return (n/2%Mod*((n-1)%Mod)%Mod*(b/m)+g(n,a,b%m,m))%Mod;
    }
    return g((a+b*n)/m,(a+b*n)%m,m,b);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Sieve();
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}*/