#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define ST first
#define ND second
#define db(v...) cerr<<#v<<"="<<v<<"\n";
#define dbr(v,x,y) FORE(_I,x,y){cerr<<#v<<"["<<_I<<"]="<<v[_I]<<"\n";}
#define dba(v) int _I=0;for(auto _it:v)cerr<<#v<<"["<<_I++<<"]="<<_it<<"\n";
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> p2ll;
const int INF=2e9;
const ll INFLL=4e18;
const int MOD=1e9+7;
const int MAXN=1e6+7;

ll ans=0;
ll n,m,k,q,t;
ll dz[3]={2,3,5};
inline ll Mn(ll v,ll w){
    if(INFLL/v>w)return v*w;
    else return INFLL;
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>t;
    while(t--){
        ll a[3],d;
        cin>>n>>a[0]>>a[1]>>a[2]>>d;
        ans=INFLL;
        priority_queue<p2ll,vector<p2ll>,greater<p2ll> > Q;
        set<ll> vis;
        Q.push({0,n});
        while(1){
            p2ll v=Q.top();
            Q.pop();
            ll num=v.ND;
            if(vis.find(num)!=vis.end())continue;
            vis.insert(num);

            if(INFLL/d>num)
            ans=min(ans,num*d+v.ST);
            if(ans<=v.ST){
                cout<<ans<<"\n";
                break;
            }
            if(num==0){
                cout<<v.ST<<"\n";
                break;
            }

            FOR(i,0,3){
                ll r=num%dz[i];

                if(r==0){
                    if(vis.find(num/dz[i])==vis.end())Q.push({v.ST+min(a[i],Mn(d,(num-num/dz[i]))),num/dz[i]});
                    num+=dz[i];
                    if(vis.find(num/dz[i])==vis.end())Q.push({v.ST+min(a[i],Mn(d,(num-num/dz[i])))+d*dz[i],num/dz[i]});
                    num-=dz[i]*2;
                    if(num>=0&&vis.find(num/dz[i])==vis.end())Q.push({v.ST+min(a[i],Mn(d,(num-num/dz[i])))+d*dz[i],num/dz[i]});
                    num+=dz[i];
                }else{
                    num-=r;
                    if(vis.find(num/dz[i])==vis.end())Q.push({v.ST+min(a[i],Mn(d,(num-num/dz[i])))+d*r,num/dz[i]});
                    num+=dz[i];
                    if(vis.find(num/dz[i])==vis.end())Q.push({v.ST+min(a[i],Mn(d,(num-num/dz[i])))+d*(dz[i]-r),num/dz[i]});
                    num-=dz[i]-r;
                }
            }


            /*r=num%3LL;
            if(r==0){
                if(vis.find(num/3LL)==vis.end())Q.push({min(b,d*(num-num/3LL)),num/3LL});
                num+=3;
                if(vis.find(num/3LL)==vis.end())Q.push({min(b,d*(num-num/3LL)),num/3LL});
                num-=6;
                if(num>=0&&vis.find(num/3LL)==vis.end())Q.push({min(b,d*(num-num/3LL)),num/3LL});
                num+=3;
            }else{
                num-=r;
                if(vis.find(num/3LL)==vis.end())Q.push({min(b,d*(num-num/3LL)),num/3LL});
                num+=3;
                if(vis.find(num/3LL)==vis.end())Q.push({min(b,d*(num-num/3LL)),num/3LL});
                num-=3-r;
            }

            r=num%5LL;
            if(r==0){
                if(vis.find(num/5LL)==vis.end())Q.push({min(c,d*(num-num/5LL)),num/5LL});
                num+=5;
                if(vis.find(num/5LL)==vis.end())Q.push({min(c,d*(num-num/5LL)),num/5LL});
                num-=10;
                if(num>=0&&vis.find(num/5LL)==vis.end())Q.push({min(c,d*(num-num/5LL)),num/5LL});
                num+=5;
            }else{
                num-=r;
                if(vis.find(num/5LL)==vis.end())Q.push({min(c,d*(num-num/5LL)),num/5LL});
                num+=5;
                if(vis.find(num/5LL)==vis.end())Q.push({min(c,d*(num-num/5LL)),num/5LL});
                num-=5-r;
            }*/
            /*if(v.ND%2LL==0LL&&vis.find(v.ND/2LL)==vis.end())Q.push({v.ST+a,v.ND/2LL});
            if(v.ND%3LL==0LL&&vis.find(v.ND/3LL)==vis.end())Q.push({v.ST+b,v.ND/3LL});
            if(v.ND%5LL==0LL&&vis.find(v.ND/5LL)==vis.end())Q.push({v.ST+c,v.ND/5LL});
            if(vis.find(v.ND+1LL)==vis.end())Q.push({v.ST+d,v.ND+1LL});
            if(vis.find(v.ND-1LL)==vis.end())Q.push({v.ST+d,v.ND-1LL});*/
        }
    }
}


Measured memory_bytes: 4452