#include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <map>

 #define ll long long

 using namespace std;

 ll a,b,p,x1,t;

 ll fast_pow(ll x,ll y,ll q)

 {

     ll ans=;

     while (y)

     {

         if (y&)    ans=ans*x%p;

         x=x*x%p;

         y>>=;

     }

     return ans;

 }

 ll ex_gcd(ll a,ll b,ll &x1,ll &y1)

 {

     if (b==)   {x1=;y1=;return a;}

     ll ans=ex_gcd(b,a%b,x1,y1);

     ll temp=x1; x1=y1; y1=temp-a/b*y1;

     return ans;

 }

 ll bsgs(ll A,ll n,ll q)

 {

     A%=q; n%=q;

     if (!A && !n)   return ;

     if (!A) return -;

     map<ll,ll> mp;

     ll m=ceil(sqrt(q));

     ll temp=fast_pow(A,m,q),k=n%q;

     mp.clear();

     for (int i=;i<=m;i++)

     {

         k=k*A%q;

         if (!mp[k]) mp[k]=i;

     }

     k=;

     for (int i=;i<=m;i++)

     {

         k=k*temp%q;

         if (mp[k])

         {

             if (mp[k]==-)    mp[k]=;

         return m*i-mp[k];

         }

     }

     return -;

 }

 ll  solve1()

 {

     ll C=(t-x1+p)%p,x,y;

     ll d=ex_gcd(b,p,x,y);

     if (C%d)    return -;

     x=x*C/d%p;

     while (x<)  x+=p;

     return x+;

 }

 ll solve2()

 {

     ll c=fast_pow(a-,p-,p)%p,B=(x1+b*c)%p,C=(b*c+t)%p,x,y;

     ll d=ex_gcd(B,p,x,y);

     if (C%d)    return -;

     while (x<) x+=p;

     ll temp=bsgs(a,x*C/d%p,p);

     if (temp!=-)   return temp+;

     else return -;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while (T--)

     {

         scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);

         if (x1==t)  puts("");

         else if (a==)  if (b==t)   puts("");

                     else    puts("-1");

     else    if (a==)   printf("%lld\n",solve1());

     else    if (a>=)    printf("%lld\n",solve2());

     }

 }