#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#define int long long
using namespace std;
int T,p,a,b,x1,t;
//先打一遍模板 
int qpow(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1)res=(res*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return res;
}
int bsgs(int a,int b,int p){
	map<int,int>mp;mp.clear();
	int m=(int)sqrt(p)+1; 
	for(int i=0;i<=m;i++)mp[b*qpow(a,i,p)]=i;
	a=qpow(a,m,p);
	for(int i=0;i<=m;i++){
		int val=qpow(a,i,p),j=mp.find(val)!=mp.end()?mp[val]:-1;
		if(j>=0&&i*t-j>=0)return i*t-j;
	}
	return -1;
}
//这道题考察的是BSGS算法，于是我们可以开始解题。 
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
		if(t==x1){puts("1");continue;}
		if(a==0&&t==b){puts("2");continue;}
		if(a==0){puts("-1");continue;}
		if(a==1&&b==0){puts("-1");continue;}
		int next=qpow(x1+b*qpow(a-1,p-2,p),p-2,p);
		printf("%d\n",bsgs(a,(t+b*qpow(a-1,p-2,p))*next,p));
	}
	return 0;
}