#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll t,n,m,k,a,b,num[2][70],p[2];
ll check(){
	cin >> n >> k >> m >> a >> b;
	if(n % m == 0)return 0;
	if(k == 1)return -1;
	if(a == 0 && b == 0)return 0;
	memset(num,0,sizeof num),p[0] = p[1] = 0;
	ll x = n,y = m,ans,pos = 0,now = n;
	while(x)num[0][++p[0]] = x % k,x /= k;
	reverse(num[0] + 1,num[0] + p[0] + 1);
	while(y)num[1][++p[1]] = y % k,y /= k;
	reverse(num[1] + 1,num[1] + p[1] + 1);
	for(ll i = 1;i <= min(p[0],p[1]);i++)
		if(num[0][i] == num[1][i])pos = i;else break;
	ans = min(p[0] * b,p[0] * b + p[1] * a - pos * a - pos * b);
	for(ll i = 0;i < p[0];i++){
		__int128_t l = now,r = now;
		for(ll j = 0;i * b + j * a < ans;j++){
			if(l / m < r / m || l % m == 0 || r % m == 0){
				ans = min(ans,i * b + j * a);
				break;
			}l *= k;r = (r + 1) * k - 1;
		}now /= k;
	}return ans;
}
int main(){
	cin >> t;
	while(t--)cout << check() << "\n";
    return 0;
}