#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

P get(ll n, ll g) {
    if (n % g == 0)
        return P(n, -1);
    else {
        ll u1 = n / g * g;
        ll u2 = n / g * g + g;
        if (n - u1 == u2 - n) {
            return P(u1, u2);
        } else if (n - u1 < u2 - n) {
            return P(u1, -1);
        } else {
            return P(-1, u2);
        }
    }
}

void solve() {
    int i, j;
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    priority_queue<ll> pq;
    pq.push(n);
    map<ll, ll> ma;
    ll ans = INF;
    while (pq.size()) {
        ll u = pq.top();
        //cout << u << endl;
        pq.pop();
        if (u >= 100 && ma.count(u + 1) && ma[u + 1] <= ma[u] - d) continue;
        if (u >= 100 && ma.count(u - 1) && ma[u - 1] <= ma[u] - d) continue;
        if (u >= 100 && ma.count(u + 2) && ma[u + 2] <= ma[u] - 2 * d) continue;
        if (u >= 100 && ma.count(u - 2) && ma[u - 2] <= ma[u] - 2 * d) continue;
        if (u < INF / d) chmin(ans, ma[u] + u * d);
        P s2 = get(u, 2);
        if (s2.fi >= 0) {
            if (ma.count(s2.fi / 2)) {
                chmin(ma[s2.fi / 2], ma[u] + (u - s2.fi) * d + a);
            } else {
                pq.push(s2.fi / 2);
                ma[s2.fi / 2] = ma[u] + (u - s2.fi) * d + a;
            }
        }
        if (s2.se >= 0) {
            if (ma.count(s2.se / 2)) {
                chmin(ma[s2.se / 2], ma[u] + (s2.se - u) * d + a);
            } else {
                pq.push(s2.se / 2);
                ma[s2.se / 2] = ma[u] + (s2.se - u) * d + a;
            }
        }
        P s3 = get(u, 3);
        if (s3.fi >= 0) {
            if (ma.count(s3.fi / 3)) {
                chmin(ma[s3.fi / 3], ma[u] + (u - s3.fi) * d + b);
            } else {
                pq.push(s3.fi / 3);
                ma[s3.fi / 3] = ma[u] + (u - s3.fi) * d + b;
            }
        }
        if (s3.se >= 0) {
            if (ma.count(s3.se / 3)) {
                chmin(ma[s3.se / 3], ma[u] + (s3.se - u) * d + b);
            } else {
                pq.push(s3.se / 3);
                ma[s3.se / 3] = ma[u] + (s3.se - u) * d + b;
            }
        }
        P s5 = get(u, 5);
        if (s5.fi >= 0) {
            if (ma.count(s5.fi / 5)) {
                chmin(ma[s5.fi / 5], ma[u] + (u - s5.fi) * d + c);
            } else {
                ma[s5.fi / 5] = ma[u] + (u - s5.fi) * d + c;
                pq.push(s5.fi / 5);
            }
        }
        if (s5.se >= 0) {
            if (ma.count(s5.se / 5)) {
                chmin(ma[s5.se / 5], ma[u] + (s5.se - u) * d + c);
            } else {
                pq.push(s5.se / 5);
                ma[s5.se / 5] = ma[u] + (s5.se - u) * d + c;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i, j;
    int t;
    cin >> t;
    while (t--) solve();
}

Measured memory_bytes: 4296