#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> memo;
ll a,b,c,d,N;
ll solve(ll n){
	if(n==0)
		return 0;
	if(n==1)
		return d;
	if(memo.count(n)){
		return memo[n];
	}
	ll l1=(n/2)*2,r1=((n+1)/2)*2;
	ll l2=(n/3)*3,r2=((n+2)/3)*3;
	ll l3=(n/5)*5,r3=((n+4)/5)*5;
	ll ret=1e18;
	
    if (n < ret/d) ret = n*d;
    
	ret=min(ret,llabs(n-l1)*d+a+solve(l1/2));
	ret=min(ret,llabs(r1-n)*d+a+solve(r1/2));
	ret=min(ret,llabs(n-l2)*d+b+solve(l2/3));
	ret=min(ret,llabs(r2-n)*d+b+solve(r2/3));
	ret=min(ret,llabs(n-l3)*d+c+solve(l3/5));
	ret=min(ret,llabs(r3-n)*d+c+solve(r3/5));
	memo[n]=ret;
	return ret;
}
ll input(){
	ll s;
	cin>>s;
	return s;
}
int main() {
	int t;
	cin>>t;
	while(t--){
		memo.clear();
		N=input();
		a=input();
		b=input();
		c=input();
		d=input();
		cout<<solve(N);
		cout<<endl;
	}

	return 0;
}
