#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
int T,mod,a,b,c,t;
namespace HASH
{
	const int N = 31700;
	const int mod = 70921;
	int key[N + 5],val[N + 5],pre[N + 5],first[mod + 5],tot;
	void clear()
	{
		tot = 0;
		memset(first,0,sizeof first);
	}
	void insert(int x,int v)
	{
		int h = x % mod;
		int flag = 0;
		for(register int i = first[h];i;i = pre[i])
			if(key[i] == x)
			{
				flag = 1;
				break;
			}
		if(!flag)
			key[++tot] = x,val[tot] = v,pre[tot] = first[h],first[h] = tot;
	}
	int query(int x)
	{
		int h = x % mod;
		for(register int i = first[h];i;i = pre[i])
			if(key[i] == x)
				return val[i];
		return -1;
	}
}
inline int fpow(int a,int b,int mod)
{
	int ret = 1;
	for(;b;b >>= 1)
		(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
	return ret;
}
inline int bsgs(int a,int b,int mod)
{
	HASH::clear();
	int lim = ceil(sqrt(mod));
	int alim = fpow(a,lim,mod);
	for(register int i = 0;i <= lim;++i)
		HASH::insert(b,i),b = (long long)b * a % mod;
	int prod = alim;
	for(register int i = 1,x;i <= lim;++i,prod = (long long)prod * alim % mod)
	{
		x = HASH::query(prod);
		if(~x)
			return i * lim - x + 1;
	}
	return -1;
}
int main()
{
	scanf("%d",&T);
	for(;T;--T)
	{
		scanf("%d%d%d%d%d",&mod,&a,&b,&c,&t);
		if(c == t)
		{
			puts("1");
			continue;
		}
		if(!a)
		{
			puts(b == t ? "2" : "-1");
			continue;
		}
		if(a == 1)
		{
			if(!b)
				puts("-1");
			else
				printf("%lld\n",(long long)(t - c + mod) * fpow(b,mod - 2,mod) % mod + 1);
			continue;
		}
		int inv = (long long)b * fpow(a - 1,mod - 2,mod) % mod;
		printf("%d\n",bsgs(a,(long long)(t + inv) * fpow(c + inv,mod - 2,mod) % mod,mod));
	}
}