#include <iostream>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define all(x) (x).begin(), (x).end()

#ifdef LOCAL
#define dbg(x) cerr << #x " = " << x << endl;
#define idbg(x) #x " = " << x
#include "pretty_print.h"
#else
#define dbg(x)
#define idbg(x) ""
#endif

#ifdef _WIN32
#  define LLD "%I64d"
#else
#  define LLD "%lld"
#endif

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }
template <typename T> T gcd(T a, T b) { return b? gcd(b, a % b) : a; }
template <typename T> bool chmin(T &x, const T& y) { if (x > y) { x = y; return true; } return false; }
template <typename T> bool chmax(T &x, const T& y) { if (x < y) { x = y; return true; } return false; }

const ll INF = (ll)5e+18+42;

ll n;
vector<ll> a(4);
vector<ll> m = {2, 3, 5, 1};
ll ans;

void rec(int idx, ll num, ll res) {
    if (idx == 3) {
        ll st = max(1LL, n / num);
        ll delta = st - 1 + abs(num * st - n);
        if (delta > ans / a[3]) {
            return;
        }
        chmin(ans, delta * a[3] + res);
        return;
    }

    rec(idx + 1, num, res);
    while (num < n) {
        num *= m[idx];
        res += a[idx];
        rec(idx + 1, num, res);
    }
}



int main(int /* argc */, char** /* argv */)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    assert(freopen("inp", "r", stdin));
    assert(freopen("out", "w", stdout));
    #endif

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < 4; ++i) {
            cin >> a[i];
        }
        // ans = INF;
        // rec(0, 1, 0);
        // ans += a[3];
        // cout << ans << "\n";

        map<pair<ll, int>, ll> mp;
        priority_queue<tuple<ll, ll, int>> h;
        mp[{n, 0}] = 0;
        h.push({0, n, 0});

        auto add = [&](ll y, int t, ll d) {
            pair<ll, int> k = {y, t};
            if (mp.count(k) && mp[k] <= d) {
                return;
            }
            mp[k] = d;
            h.push({-d, y, t});
        };

        ll res = INF;

        while (h.size()) {
            auto [d, x, t] = h.top();
            d = -d;
            h.pop();
            if (mp[{x, t}] != d) {
                continue;
            }
            ll delta = abs(x);
            if (delta <= res / a[3]) {
                res = min(res, d + a[3] * delta);
            }
            for (int i = 0; i < 3; ++i) {
                if (x % m[i] == 0) {
                    add(x / m[i], 0, d + a[i]);
                }
            }
            if (t == 0) {
                for (int i = 1; i <= 5; ++i) {
                    add(x + i, 1, d + a[3] * i);
                    add(x - i, 1, d + a[3] * i);
                }
            }
        }
        cout << res << "\n";
        // ll x = 0;
        // while (x != n) {
        //     dbg(x);
        //     x = pr[x];
        // }
        // assert(ans == mp[0]);
// #endif
    }

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}


Measured memory_bytes: 15920