#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T chmin(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T chmax(T& l, T r) {
    return l = max(l, r);
}
// ============ template finished ============

bool update(map<ll, ll>& mp, ll score, ll number) {
    if (mp.find(number) == mp.end()) {
        mp[number] = score;
        return true;
    }
    else {
        ll baseScore = mp[number];
        if (baseScore <= score) {
            return false;
        }
        else {
            mp[number] = score;
            return true;
        }
    }
}

int main()
{
    int T;
    cin >> T;
    rep(t, T) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;
        //priority_queue<pll, vector<pll>, greater<pll>> pq; // <score, number>
        set<ll> finds;
        map<ll, ll> mp; // number -> score
        //pq.push({ 0,N });
        finds.insert(N);
        mp[N] = 0;
        while (!finds.empty()) {
            // ll nowScore, nowNumber;
            // tie(nowScore, nowNumber) = pq.top(); pq.pop();
            auto itr = finds.end(); --itr;
            ll nowNumber = *itr;
            finds.erase(nowNumber);
            ll nowScore = mp[nowNumber];
            if (nowNumber == 0)break;
            if (nowNumber == 1) {
                update(mp, nowScore + D, 0);
                break;
            }

            // special case: use all D
            {
                if (log10(nowNumber) + log10(D) < 18.8) {
                    update(mp, nowScore + nowNumber * D, 0);
                }
            }

            // updater2
            if (nowNumber % 2 == 0) {
                ll nextNumber = nowNumber / 2;
                ll nextScore = nowScore + A;
                if (update(mp, nextScore, nextNumber)) {
                    finds.insert(nextNumber);
                    // pq.push({ nextScore,nextNumber });
                }
            }
            else {
                REP(nextNumber, nowNumber / 2, nowNumber / 2 + 2) {
                    ll timeD = abs(nextNumber * 2 - nowNumber);
                    ll nextScore = nowScore + D * timeD + (nextNumber == 0 ? 0 : A);
                    if (update(mp, nextScore, nextNumber)) {
                        finds.insert(nextNumber);
                        // pq.push({ nextScore,nextNumber });
                    }
                }
            }

            // updater3
            if (nowNumber % 3 == 0) {
                ll nextNumber = nowNumber / 3;
                ll nextScore = nowScore + B;
                if (update(mp, nextScore, nextNumber)) {
                    finds.insert(nextNumber);
                    // pq.push({ nextScore,nextNumber });
                }
            }
            else {
                REP(nextNumber, nowNumber / 3, nowNumber / 3 + 2) {
                    ll timeD = abs(nextNumber * 3 - nowNumber);
                    ll nextScore = nowScore + D * timeD + (nextNumber == 0 ? 0 : B);
                    if (update(mp, nextScore, nextNumber)) {
                        finds.insert(nextNumber);
                        // pq.push({ nextScore,nextNumber });
                    }
                }
            }

            // updater5
            if (nowNumber % 5 == 0) {
                ll nextNumber = nowNumber / 5;
                ll nextScore = nowScore + C;
                if (update(mp, nextScore, nextNumber)) {
                    finds.insert(nextNumber);
                    // pq.push({ nextScore,nextNumber });
                }
            }
            else {
                REP(nextNumber, nowNumber / 5, nowNumber / 5 + 2) {
                    ll timeD = abs(nextNumber * 5 - nowNumber);
                    ll nextScore = nowScore + D * timeD + (nextNumber == 0 ? 0 : C);
                    if (update(mp, nextScore, nextNumber)) {
                        finds.insert(nextNumber);
                        // pq.push({ nextScore,nextNumber });
                    }
                }
            }
        }
        cout << mp[0] << endl;
    }

    return 0;
}


Measured memory_bytes: 4792