#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int __int128
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
int n,k,m,a,b,res;
__int128 qmi(__int128 x,int y) {
	__int128 res=1;
	while(y) {
		if(y&1) res=res*x;
		x=x*x;
		y>>=1;
	}return res;
}
bool check(int c,int n,__int128 m) {
	__int128 now=(__int128)(qmi(k,c)*n); 
	m=(m+now-1)/m*m;
	m-=now;
	rep1(i,c-1,1) {
		now=qmi(k,i);
		m-=min(k-1,(int)(m/now))*now;
	}
	return (m<=k-1);
}
int cc(int k,int x,int r) {
	r/=x;
	int cnt=false;
	while(r) r/=k,cnt++;
	return cnt;
}
int gets(int x,int y) {
	int l=1,r=max((int)8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
	rep(i,l,r) if(check(i,x,y)) res=min(res,i);
	return res*a;
}
void solve() {
	in(n),in(k),in(m),in(a),in(b);
	if(n%m==0) {
		cout<<"0\n";
		return;
	}else if(k==1) {
		puts("-1");
		return;
	}
	res=LONG_LONG_MAX;
	int now=0;
	while(n) {
		res=min(res,now+gets(n,m));
		n/=k;
		now+=b;
		if(n%m==0) res=min(res,now);
	}
	res=min(res,now);
	print(res);
	cout<<endl;
}
fire main() {
//	freopen("transform.in","r",stdin);
//	freopen("transform.out","w",stdout);
	in(T);
	while(T--) {
		solve();
	}
	return false;
}
/*
1
2157584874927409 3499113 70686381 77518537 690462406
*/