#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=5e5+5;
const int MM=25e5+5;
int A,B,C,D;
ll n;
map<ll,ll>f;
set<ll>S;
ll dfs(ll n){
	if(!n)return 0;
	if(f.count(n))return f[n];
	reg ll res;
	if((double)n*D>9e18)res=9e18;
	else res=n*D;
	for(reg ll i=max(0ll,n-5);i<=n+5;i++){
		if(i%2==0&&i/2<n)res=min(res,dfs(i/2)+llabs(i-n)*D+A);
		if(i%3==0&&i/3<n)res=min(res,dfs(i/3)+llabs(i-n)*D+B);
		if(i%5==0&&i/5<n)res=min(res,dfs(i/5)+llabs(i-n)*D+C);
	}
	return f[n]=res;
}
int main(){
	reg int T;scanf("%d",&T);
	while(T--){
		scanf("%lld%d%d%d%d",&n,&A,&B,&C,&D);
		f.clear();printf("%lld\n",dfs(n));
	}
	return 0;
}