#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,p,x,t;
int ksm(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=(res*a)%p;
		a=(a*a)%p;
		b/=2;
	}
	return res;
}
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int inv(int a,int p)
{
	return ksm(a,p-2,p);
}
int bsgs(int a,int b,int p)
{
	a%=p; b%=p;
	if(b==1) return 0;
	unordered_map<int,int> mp;
	int m=ceil(sqrt(p));
	int am=ksm(a,m,p);
	for(int j=0;j<=m;j++)
	{
		if(!mp.count(b)) mp[b]=j;
		b=b*a%p;
	}
	int mul=1;
	for(int i=1;i<=m;i++)
	{
		mul=mul*am%p;
		if(mp.count(mul)) return i*m-mp[mul]+1;
	}
	return -1;
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>p>>a>>b>>x>>t;
		if(x==t) {cout<<1<<"\n";continue;}
		if(a==0) {if(t==b) cout<<2<<"\n"; else cout<<"-1\n"; continue;}
		if(a==1&&b==0) {cout<<-1<<"\n";continue;}
		if(a==1)
		{
			int invb=inv(b,p);
			int ans=(((t-x)%p+p)%p)*invb%p;
			cout<<ans+1<<"\n";
			continue;
		}
		int xxx=(t+b*inv(a-1,p)%p)%p*inv(x+b*inv(a-1,p)%p,p)%p;
		int ans=bsgs(a,xxx,p);
		cout<<ans<<"\n";
	}
	return 0;
}