被取模卡了一天...............
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {if(!b) g=a,x=1,y=0;else exgcd(b,a%b,g,y,x),y-=(a/b)*x;}ll p,a,b,x1,t;
/
ll pw(ll a, ll b) {ll r = 1;while(b) {if(b & 1) r = r*a%p; a = a*a%p, b >>= 1;}return r;
}
ll bsgs(ll a, ll b,ll p) {ll m = sqrt(p)+1, e = 1,g,x,y;exgcd(pw(a, m), p, g, x, y);ll ni = (x % p + p) % p;map<ll, ll> mp;mp[1] = 0;for(int i = 1; i < m; i++) {e = e*a%p;if(!mp.count(e)) mp[e] = i;}for(int i = 0; i < m; i++) {if(mp.count(b)) return i*m+mp[b];b = b*ni%p;}return -2;
}
//
void work()
{scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t); if (t==x1) {puts("1");return;}if (a==0){if (t==b) puts("2");else puts("-1");return ;}if (a==1){if (!b) {puts("-1");return ;}ll d,x,y;exgcd(b,p,d,x,y);x=x*(t-x1);x=(x%p+p)%p;printf("%lld\n",x+1);return ;}ll d,x,y;exgcd(a-1,p,d,x,y);ll c=(x%p+p)%p;exgcd((x1+b*c)%p,p,d,x,y);if ((b*c+t)%d) {puts("-1");return;}x=x*((b*c+t)/d)%(p/d);x=(x%(p/d)+(p/d))%(p/d);printf("%lld\n",bsgs(a,x,p)+1);
}int main()
{ll T;scanf("%lld",&T);while (T--) work(); return 0;
}