#include<cstdio>
#include<cmath>
#include<map>
#define int long long
inline int sqrt(int sqrtner){
	if(sqrtner<4){
		return 1;
	};
	int low=0,high=sqrtner;
	while(low<high){
		int middle=(low+high+1)>>1;
		if(middle*middle>sqrtner){
			high=middle-1;
		}else{
			low=middle;
		};
	};
	if(low*low>sqrtner){
		return high;
	};
	return low;
};
inline int power(int first,int second,int mod){
	int result=1;
	while(second){
		if(second&1){
			(result*=first)%=mod;
		};
		(first*=first)%=mod;
		second>>=1;
	};
	return result;
};
inline int exgcd(int first,int second,int &answer1,int &answer2){
	if(!second){
		answer1=1;
		answer2=0;
		return first;
	};
	int gcd=exgcd(second,first%second,answer1,answer2),tmp=answer1;
	answer1=answer2;
	answer2=tmp-first/second*answer2;
	return gcd;
};
inline int baby_step_giant_step(int first,int second,int mod){
	std::map<int,int> hash;
	if(second==1){
		return 0;
	};
	if(!(first%mod)){
		if(!second){
			return 1;
		};
		return -2;
	};
	second%=mod;
	int sqrtner=sqrt(mod)+2,tmp=second,factor=power(first,sqrtner,mod);
	for(int iter=1;iter<=sqrtner;++iter){
		(tmp*=first)%=mod;
		hash[tmp]=iter;
	};
	tmp=1;
	for(int iter=1;iter<=sqrtner;++iter){
		(tmp*=factor)%=mod;
		if(hash.count(tmp)){
			return ((iter*sqrtner-hash[tmp])%mod+mod)%mod;
		};
	};
	return -2;
};
signed main(signed,char**){
	int test,answer1=0,answer2=0;
	scanf("%lld",&test);
	while(test--){
		int mod,first,second,start,finish;
		scanf("%lld %lld %lld %lld %lld",&mod,&first,&second,&start,&finish);
		if(start==finish){
			puts("1");
		}else if(!first){
			if(second==finish){
				puts("2");
			}else{
				puts("-1");
			};
		}else if(first==1){
			int flag=((finish+second-start)%mod+mod)%mod,gcd=exgcd(second,mod,answer1,answer2),answer;
			if(flag%gcd){
				puts("-1");
			}else{
				answer1*=flag/gcd;
				answer=(answer1%mod+mod)%mod;
				if(answer){
					printf("%lld\n",answer);
				}else{
					printf("%lld\n",mod);
				};
			};
		}else{
			int arg1=first,arg2=(first*finish%mod-finish+second)*power((first*start%mod-start+second),mod-2,mod);
			printf("%lld\n",baby_step_giant_step(arg1,arg2,mod)+1);
		};
	};
	return 0;
};