#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
queue<pair<ll, ll>> q;
ll C[10];
ll N, D;

void reg(ll rest, ll cost, ll r, map<ll,ll>& mp){
    ll re = rest % r;
    // 余り0
    if(re == 0){
        if(1.0L * D * (rest - rest / r) + cost> 1e18)
            cost = cost + C[r];
        else 
            cost = min(D * (rest - rest / r) + cost, cost + C[r]);
        if(mp.find(rest/r) == mp.end()){
            mp[rest / r] = cost;
            q.emplace(rest / r, cost);
        }
        else{
            if(chmin(mp[rest/r], cost))
                q.emplace(rest / r, cost);
        }
    }
    // 0以外
    else{
        ll r1 = (rest + r)/r, r2 = rest/r, d1 = D * (r - re), d2 = D * re;

        ll c1, c2;
        if(1.0L * D * (rest - r1) > 1e18 or 1.0L * D * (rest - r2) > 1e18)
            c1 = cost + d1 + C[r], c2 = cost + d2 + C[r];
        else{
            c1 = min(cost + d1 + C[r], D * (rest - r1) + cost), c2 = min(cost + d2 + C[r], D * (rest - r2) + cost);
        }
        // err(c1, c2, d1, d2);

        if(mp.find(r1) == mp.end()){
            mp[r1] = c1;
            q.emplace(r1, c1);
        }
        else{
            if(chmin(mp[r1], c1))
                q.emplace(r1, c1);
        }
        if(mp.find(r2)==mp.end()){
            mp[r2] = c2;
            q.emplace(r2, c2);
        }
        else{
            if(chmin(mp[r2], c2))
                q.emplace(r2, c2);
        }
    }
}
int main() {
    init();
    ll T;
    cin >> T;
    while(T--){
        cin >> N >> C[2] >> C[3] >> C[5] >> D;
        map<ll, ll> mp;
        // map<ll, bool> mpb;

        q.emplace(N, 0);
        while(!q.empty()){
            ll rest, cost;
            tie(rest, cost) = q.front(), q.pop();
            if (rest <= 1) continue;
            if (mp[rest] < cost) continue;

            // 2
            reg(rest, cost, 2, mp);
            // 3
            reg(rest, cost, 3, mp);
            // 5
            reg(rest, cost, 5, mp);
        }

        cout << mp[1] + D << endl;
    }
}

Measured memory_bytes: 4508