#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,int> hash;
int T;
ll p,a,b,x1,xn;
ll ksm(int a,int x,int m)//return (a^x)%m
{
	int t=1;
	while(x)
	{
		if(x&1) t=t*a%m;
		a=a*a%m;
		x>>=1;
	}
	return t;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){x=1,y=0;return a;}
	ll g=exgcd(b,a%b,x,y),last_x=x;
	x=y,y=last_x-a/b*y;
	return g;
}
ll bsgs(ll a,ll b,ll p)
{
	hash.clear();
	ll m=ceil(sqrt(p));
	for(int j=0;j<=m;j++)
	hash[b]=j,b=b*a%p;
	ll am=ksm(a,m,p),ami=1;
	for(int i=1;i<=m;i++)
	{
		ami=ami*am%p;
		if(hash.find(ami)!=hash.end())
		return i*m-hash[ami]+1;
	}
	return -1;
}
int main()
{
    cin>>T;
    while(T--)
    {
    	cin>>p>>a>>b>>x1>>xn;
    	if(x1==xn) {cout<<1<<endl;continue;}
    	if(a==0)
    	{
    		if(xn==b) {cout<<2<<endl;continue;}
    		else{cout<<-1<<endl;continue;}
    	}
    	else if(a==1)
    	{
    		if(b==0){cout<<-1<<endl;continue;}
    		ll x0,y0,g=exgcd(b,p,x0,y0),c=xn-x1,delta=abs(p/g);
    		if(c%g) {cout<<-1<<endl;continue;}
    		else{x0=x0*c/g;x0=(x0%delta+delta)%delta+1;cout<<x0<<endl;continue;}
    	}
    	else
    	{
    		ll c=(xn+b*ksm(a-1,p-2,p))%p,d=(x1+b*ksm(a-1,p-2,p));
    		c=c*ksm(d,p-2,p);
    		cout<<bsgs(a,c,p)<<endl;
    	}
    }
	return 0;
}
/*
1
59 1 0 11 56
*/