#include<map>#include<cmath>#include<cstdio>#include<iostream>#define ll long longusing namespace std;inline int read(){    int x=0;char ch=getchar();    while(ch<‘0‘||ch>‘9‘)ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x;}int T;ll p,a,b,x1,t;ll exgcd(ll a,ll b,ll &x,ll &y){    if(!b){x=1;y=0;return a;}    ll tmp=exgcd(b,a%b,x,y);    ll t=x;x=y;y=t-a/b*y;    return tmp;}ll fpow(ll a,ll b,ll p){    ll res=1;    for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;    return res;}map<ll,int> mp;ll BSGS(ll A,ll B,ll C){    A%=C;    if(!A){        if(!B)return 1;        return -1;     }    ll m=sqrt(C)+1,t=1,I=1,Im=fpow(A,C-1-m,C);    mp.clear();mp[1]=m+1;    for(int i=1;i<m;i++){        t=t*A%C;        if(!mp[t])mp[t]=i;    }    for(int k=0;k<m;k++){        int i=mp[B*I%C];        if(i){            if(i==m+1)i=0;            return k*m+i;        }        I=I*Im%C;    }    return -1;}ll cal1(){    ll C=(t-x1+p)%p,x,y;    ll t=exgcd(b,p,x,y);    if(C%t)return -1;C/=t;    x=x*C%p;    if(x<0)x+=p;    return x+1;}ll cal2(){    ll c=fpow(a-1,p-2,p),A=(x1+b*c)%p,C=(t+b*c)%p,x,y;    ll t=exgcd(A,p,x,y);    if(C%t)return -1;C/=t;    if(x<p)x=x%p+p;    t=BSGS(a,x*C%p,p);    if(t!=-1)return t+1;    return -1;}ll solve(){    if(x1==t)return 1;    if(a==0){        if(b==t)return 2;        return -1;    }    if(a==1)return cal1();    else return cal2();}int main(){    T=read();    while(T--){        p=read();a=read();b=read();x1=read();t=read();        printf("%lld\n",solve());    }    return 0;}