#include<bits/stdc++.h>
using namespace std;
inline __int128 read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch)){
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
void out(__int128 x){
	if(x>9){
		out(x/10);
	}
	putchar(x%10+'0');
}
inline void solve(){
	__int128 n,k,m,a,b;
	n=read();k=read();m=read();a=read();b=read();
	if(n%m==0){
		cout<<"0\n";
		return;
	}
	if(k==1){
		cout<<"-1\n";
		return;
	}
	__int128 ans=4e18;
	__int128 s=0;
	while(n){
		__int128 now=s;
		__int128 x=n,y=n;
		if(n%m==0){
			ans=min(ans,now);
		}
		while(y<2e18){
			now+=a;
			x*=k;y=y*k+k-1;
			if(y/m-(x-1)/m){
				ans=min(ans,now);
			}
		}
		n/=k;
		s+=b;
	}
	ans=min(ans,s);
	out(ans);
	cout<<'\n';
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
}