#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PII;
void solve()
{
	ll n,k,m,a,b;
	cin>>n>>k>>m>>a>>b;
	if(k==1)
	{
		if(n%m==0) cout<<0<<endl;
		else cout<<-1<<endl;
	}
	else
	{
		if(n%m==0) cout<<0<<endl;
		else
		{
			ll tt=n,ans=0;
			while(tt)
			{
				ans+=b;
				tt/=k;
			}
			vector<ll>num;
			vector<ll>init;
			ll temp=0;
			while(n)
			{
				num.push_back(n);
				init.push_back(temp);
				n/=k;
				temp+=b;
			}
			auto get_ans=[&](ll x,ll res)->ll
			{
				ll l,r;
				l=r=x%m;
				if(l==0) return res;
				for(ll i=1;i<=30;i++){
					l=k*l;r=k*r+k-1;
					res+=a;
					if(l/m!=r/m) return res;
					l=l%m;r=r%m;
					if(l==0||r==0) return res;
				}
			};
			for(int i=0;i<num.size();i++)
				ans=min(ans,get_ans(num[i],init[i]));
			cout<<ans<<endl;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)
		solve();
	return 0;
}