#include<stdio.h>
#include<ctype.h>
#include<vector>
#include<math.h>
namespace IO {
	constexpr int bufsize = 230005;
	char buf[bufsize], *f1, *f2;
	#define gtchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
	template<typename t> void read(t &ret)
	{
		int f = ret = 0;
		char ch = gtchar();
		while(!isdigit(ch)) f = ch == '-', ch = gtchar();
		while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
		if(f) ret = -ret;
	}
	#undef gtchar
	template<typename t, typename ...T> void read(t &a, T &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
int T, k, m, inf;
ll n, A, B;
ll min(ll a, ll b) {return a > b? b: a;}
ll qpow(ll a, int b)
{
	a %= m;
	ll ret = 1;
	while(b)
	{
		if(b & 1) ret = ret * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return ret;
}
bool check(ll n, int p)
{
	ll goal = n % m * qpow(k, p) % m;
	goal = goal? m - goal: 0;
	return !goal || log(goal) < p * log(k);
}
int solve(ll x)
{
	int l = 0, r = inf;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(check(x, mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}
int main()
{
//	freopen("transform.in", "r", stdin);
//	freopen("transform.out", "w", stdout);
	read(T);
	while(T--)
	{
		read(n, k, m, A, B);
		if(k == 1)
		{
			puts(n == m? "0": "-1");
			continue;
		}
		inf = ceill(log(m) / log(k)) + 5;
		std::vector<ll> tmp;
		while(n) tmp.push_back(n), n /= k;
		ll ans = 1e18;
		tmp.push_back(0);
		bool f = false;
		for(int i = 0; i < tmp.size(); i++)
		{
			int t = solve(tmp[i]);
			if(t != inf) ans = min(ans, i * B + t * A), f = true;
		}
		printf("%lld\n", f? ans: -1);
	}
	return 0;
}