#include<bits/stdc++.h>
#define N 10000000
#define mod 998244353
using namespace std;
int power(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y=y/2;
	}
	return res;
}
int phi[N+5],p[1000005],cp;
bool bl[N+5];
void init(){
	phi[1]=1;
	for(int i=2;i<=N;i++){
		if(!bl[i]) p[++cp]=i,phi[i]=i-1;
		for(int j=1;j<=cp&&p[j]*i<=N;j++){
			bl[i*p[j]]=1;
			if(i%p[j]==0){
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
}
int t,m,a,b,c,d,ans;
long long L,R,n;
int main(){
	init();
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d%d",&m,&a,&b,&c,&d);
		L=(a==0||b==0)?0:power(m,__gcd(a,b));
		R=(c==0||d==0)?0:power(m,__gcd(c,d));
		n=R-L;ans=0;
		int u=m;
		while(u%2==0) u/=2;
		for(int i=1;i*i<=u;i++){
			if(m%i==0){
				ans=(ans+1ll*power(2,n/u*i)*phi[u/i])%mod;
				if(i*i!=u) ans=(ans+1ll*power(2,n/i)*phi[i])%mod;
			}
		} 
		ans=1ll*ans*power(m,mod-2)%mod;
		printf("%d\n",ans);
	}
}