#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

template<typename T>
struct Compress {
private:
    vector<T> value;
    
public:
    Compress(const vector<T> &v, bool distinct = false) {
        int n = v.size();
        value.resize(n);
        value = v;
        sort(value.begin(), value.end());
        if (distinct) value.erase(unique(value.begin(), value.end()), value.end());
    }
    
    int size() {
        return value.size();
    }
    
    int val(int idx) {
        return value[idx];
    }
    
    int get(int v) {
        return lower_bound(value.begin(), value.end(), v) - value.begin();
    }
};

const ll inf = LONG_LONG_MAX / 2 - 1;

vector<ll> get_step(ll v) {
    set<ll> tmp1, tmp2;
    const ll kkr[] = {2, 3, 5};
    rep(i, 3) {
        ll cv = 1;
        while(cv <= v) {
            tmp1.insert(cv);
            cv *= kkr[i];
        }
    }
    for(auto &x : tmp1) {
        tmp2.insert(x - 1);
        tmp2.insert(x);
        tmp2.insert(x + 1);
    }
    vector<ll> ans(sz(tmp2));
    ll idx = 0;
    for(auto &x : tmp2) {
        ans[idx++] = x;
    }
    return ans;
}

void solve() {
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    vector<ll> step = get_step(n);
    Compress<ll> cmp(step);
    vector<ll> dp(cmp.size(), inf);
    dp[0] = 0;
    reps(i, 1, cmp.size()) {
        ll v = step[i];
        if (v % 2 == 0) {
            dp[i] = min(dp[i], dp[cmp.get(v / 2)] + a);
        }
        if (v % 3 == 0) {
            dp[i] = min(dp[i], dp[cmp.get(v / 3)] + b);
        }
        if (v % 5 == 0) {
            dp[i] = min(dp[i], dp[cmp.get(v / 5)] + c);
        }
        dp[i] = min(dp[i], dp[i - 1] + d);
        if (i < (cmp.size() - 1)) {
            dp[i] = min(dp[i], dp[i + 1] + d);
        }
    }
    cout << dp[cmp.get(n)] << endl;
    rep(i, cmp.size()) {
        printf("dp[%lld] = %lld\n", cmp.val(i), dp[i]);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
    ll t;
    cin >> t;
    rep(i, t) solve();
    return 0;
}
