#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<map> using namespace std; typedef long long ll; struct Thash{ static const int MOD=233333; static const int MAXN=1e6+5; int tot,head[MOD+100],next[MAXN],h[MAXN],val[MAXN]; inline void clear(){tot=0;memset(head,0,sizeof head);} inline void insert(int H,int VAL){ for(int i=head[H%MOD];i;i=next[i]) if(h[i]==H){val[i]=VAL;return ;} next[++tot]=head[H%MOD];head[H%MOD]=tot;h[tot]=H;val[tot]=VAL; } inline int get(int H){ for(int i=head[H%MOD];i;i=next[i]) if(h[i]==H) return val[i]; return 0; } }M; int T; ll p,a,b,x1,t; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll fpow(ll a,ll p,ll mod){ ll res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res; } void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ if(!b){d=a;x=1;y=0;return ;} exgcd(b,a%b,d,y,x); y-=x*(a/b); } ll BSGS(ll A,ll B,ll mod){ A%=mod; if(!A){ if(!B) return 1; return -1; } ll m=sqrt(mod)+1,ni=fpow(A,mod-m-1,mod); ll t=1,y=1; M.clear(); M.insert(1,m+1); for(int i=1;i<m;i++){ t=t*A%mod; if(!M.get(t)) M.insert(t,i); } for(int i=0;i<m;i++){ int u=M.get(B*y%mod); if(u){ if(u==m+1) u=0; return i*m+u; } y=y*ni%mod; } return -1; } ll calc1(){ ll z=(t-x1+p)%p,d,x,y; exgcd(b,p,d,x,y); if(z%d) return -1;z/=d; x=x*z%p; if(x<0) x+=p; return x+1; } ll calc2(){ ll c=fpow(a-1,p-2,p),A=(x1+b*c)%p,z=(b*c+t)%p,d,x,y; exgcd(A,p,d,x,y); if(z%d) return -1;z/=d; if(x<p) x=x%p+p; d=BSGS(a,x*z%p,p); if(~d) return d+1; return -1; } ll solve(){ if(x1==t) return 1; if(!a){ if(b==t) return 2; else return -1; } if(a==1) return calc1(); return calc2(); } int main(){ freopen("random.in","r",stdin); freopen("random.out","w",stdout); for(T=read();T--;){ p=read();a=read();b=read();x1=read();t=read(); printf("%lld ",solve()); } return 0; }