#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int P=998244353;
typedef long long ll;
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
ll getpw(ll a,int b){
	ll res=1;
	while(b){
		if(b&1){
			res*=a;
			if(b==1) return res;
		}
		a*=a;b>>=1;
	}
	return res;
}
const int N=10000003;
const int E=1e7;
int phi[N];
int pr[N],rk;
bool vis[N];
void solve(){
	int m=read();
	int a=read(),b=read(),c=read(),d=read();
	int l=__gcd(a,b),r=__gcd(c,d);
	ll L=getpw(m,l),R=getpw(m,r);
	// assert(L<R);
	ll T=R/m-L/m;
	int mm=m>>__builtin_ctz(m);
	int cur=0,pp=qp(2,T%(P-1)*(m&-m)%(P-1));
	auto proc=[&](int x){cur=(cur+(ll)qp(pp,x)*phi[mm/x]%P);};
	for(int i=1;i*i<=mm;++i)
		if(mm%i==0){
			proc(i);
			if(i*i<mm) proc(mm/i);
		}
	cur=(ll)cur*qp(m)%P;
	printf("%d\n",cur);
}
int main(){
	// freopen("calculate.in","r",stdin);
	// freopen("calculate.out","w",stdout);
	phi[1]=1;
	for(int i=2;i<=E;++i){
		if(!vis[i]){pr[++rk]=i;phi[i]=i-1;}
		for(int j=1;j<=rk;++j){
			int cur=i*pr[j];
			if(cur>E) break;
			vis[cur]=1;
			if(i%pr[j]) phi[cur]=phi[i]*(pr[j]-1);
			else{phi[cur]=phi[i]*pr[j];break;}
		}
	}
	int tc=read();
	while(tc--) solve();
	return 0;
}