今天下午比赛T1挂了……

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int md=998244353;
int t,n,a,b,x,y,f1[100005],f2[100005],ans=1;
int ksm(int x,int d)
{
	int res=1,base=(x%md+md)%md;
	while(d)
	{
		if(d&1)res=res*base%md;
		base=base*base%md;
		d>>=1;
	}
	return res;
}
signed main()
{
	cin>>t;
	while(t--)
	{
		int t1=1e6,t2=1e6,mx,mn;ans=1;
		scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&x,&y);
		f1[1]=a,f1[2]=b;f2[1]=x,f2[2]=y;
		for(int i=3;i<=n;++i)
		{
			long double tp=1.0*f1[i-2]*f1[i-1];
			f1[i]=(int)(sqrtl(tp)+1);
			if(f1[i]==f1[i-1])
			{
				t1=i;break;
			}
		}
		for(int i=3;i<=n;++i)
		{
			long double tp=1.0*f2[i-2]*f2[i-1];
			f2[i]=(int)(sqrtl(tp)+1);
			if(f2[i]==f2[i-1])
			{
				t2=i;break;
			}
		}
		mx=max(t1,t2);mx=min(n,mx);
		mn=min(t1,t2);
		for(int i=1;i<=mx;++i)
		{
			if(i>t2)
			{
				long double tp=1.0*f2[i-2]*f2[i-1];
				f2[i]=(int)(sqrtl(tp)+1);
			}
			if(i>t1)
			{
				long double tp=1.0*f1[i-2]*f1[i-1];
				f1[i]=(int)(sqrtl(tp)+1);
			}
			ans*=(f2[i]-f1[i]);
			ans=(ans%md+md)%md;
		}
		if(mx==n)
		{
			cout<<ans<<endl;continue;
		}
		if((mx-mn)%2==0)
		{
			int cha=f2[mx]-f1[mx];
			ans=ans*ksm(cha,n-mx)%md;
		}
		else
		{
			int cha1=f2[mx]-f1[mx],cha2=f2[mx-1]-f1[mx-1],s1,s2;
			s1=(n-mx)/2;s2=(n-mx+1)/2;
			ans=ans*ksm(cha1,s1)%md*ksm(cha2,s2)%md;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
4
5 2 10 1 8
11 4 5 1 4
19 1 9 8 10
114 51 4 1919 810
2
1147 18879325 66700235 20590764 6758435
34729 759303 75829031 90835 68970421
*/