#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#include<memory>
#include<numeric>
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
    
using namespace std;
    
using ll=long long;
using ld =long double;
    
#define WHATS(var)//cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
    
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
    os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
    for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
    for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
    for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
    int i=0;
    for(auto it:v){
        if(i > 0){os << ' ';}
        os << it;
        i++;
    } 
    return os;
}
using Graph=vector<vector<int>>;
 
 
const int mod = 998244353;



bool operator<(const vector<int>&lv,const vector<int>&rv){
    
    if(lv.size()!=rv.size()){
        return lv.size()<rv.size();
    }else{
        for(int i=0;i<lv.size();++i){
            if(lv[i]!=rv[i]){
                return lv[i]<rv[i];
            }
        }
        return false;
    }
}

ll gcd(ll a,ll b){
    if(a%b==0)return b;
    else{
        return gcd(b,a%b);
    }
}

int gettp(int x,int y,int cx,int cy){
    return int (x>=cx) + int(y>=cy)*2;
}

string to(vector<int>v){
    string st;
    for(auto x:v){
        char ch;
        if(x<26)ch='a'+x;
        else if(x<52)ch='A'+(x-26);
        else ch='0'+(x-52);
        st.push_back(ch);
    }
    return st;
}

const int SIX_TWO=62;

vector<int>fin_answer;
int len;
int all_a_cnt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    int T;cin>>T;
    while(T--){
        ll N,A,B,C,D;cin>>N>>A>>B>>C>>D;
        vector<ll>ABC{A,B,C};
        priority_queue<pair<ll,ll>>que;
        que.emplace(0,N);
        ll answer=1e18;
        vector<int>primes{2,3,5};
        map<ll,ll>mp;
        while(!que.empty()){
            auto q(que.top());
            que.pop();
            WHATS(q)
            ll now_cost=-q.first;
            ll now=q.second;
            
            WHATS(now)
            if(now<0){
                return 0;
            }
            if(ld(now)*D<1e18){
                answer=min(answer,mp[now]+now*D);
            }
            vector<int>flags(3);
            for(ll nex=now;nex<now+10;++nex){
                for(int i=0;i<3;++i){
                    if(nex%primes[i]==0&&!flags[i]){
                        flags[i]=true;
                        ll nex_cost=now_cost+D*abs(nex-now)+ABC[i];
                        ll nn=nex/primes[i];

                        if(mp.find(nn)==mp.end()||mp[nn]>nex_cost){
                            mp[nn]=nex_cost;
                            que.emplace(-nex_cost,nn);
                        }
                    }
                }
                if(flags[0]&&flags[1]&&flags[2])continue;
            }
            flags=vector<int>(3,0);
            for(ll nex=now;nex>max(0ll,now-10);--nex){
                for(int i=0;i<3;++i){
                    if(nex%primes[i]==0&&!flags[i]){
                        flags[i]=true;
                        ll nex_cost=now_cost+D*abs(nex-now)+ABC[i];
                        ll nn=nex/primes[i];

                        if(mp.find(nn)==mp.end()||mp[nn]>nex_cost){
                            mp[nn]=nex_cost;
                            que.emplace(-nex_cost,nn);
                        }
                    }
                }
                if(flags[0]&&flags[1]&&flags[2])continue;
            }
        }
        cout<<answer<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 4264