#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(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
*/

answer.code: In function ‘__int128 gets(__int128, __int128)’:
answer.code:55:22: error: no matching function for call to ‘max(long long int, __int128)’
   55 |         int l=1,r=max(8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:55:22: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘__int128’)
   55 |         int l=1,r=max(8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:55:22: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘__int128’)
   55 |         int l=1,r=max(8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:55:22: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   55 |         int l=1,r=max(8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:55:22: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   55 |         int l=1,r=max(8ll,cc(k,x,1000000000000000000)),res=INT_MAX;
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~