#include <bits/stdc++.h>

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int i=(first);i<(last);++i){cout<<#a<<"["<<i<<"] = "<<(a)[i]<<endl;}
#define PRINTP(p)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#p<<" = ("<<(p.first)<<", "<<(p.second)<<")"<<endl;
#define PRINTI(a,i)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<#i<<"] = "<<#a<<"["<<(i)<<"] = "<<(a)[i]<<endl;
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#define PRINTP(p)
#define PRINTI(a,i)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using u128 = __int128;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

template <class T>
using vec2 = vector<vector<T>>;

template <class T>
using vec3 = vector<vector<vector<T>>>;

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int T;
    cin >> T;
    while (T--) {
        ll N;
        vector<int> A(3);
        int D;
        cin >> N >> A[0] >> A[1] >> A[2] >> D;

        vector<int> primes = {2, 3, 5};

        map<ll, u128> m;
        m[0] = 0;

        function<u128(ll)> f = [&](ll n) {
            if (m.count(n)) {
                return m[n];
            }
            u128 tmp = (u128) n * D;
            REP(i, primes.size()) {
                int p = primes[i];
                ll k0 = n / p;
                ll k1 = (n + p - 1) / p;
                ll y0 = k0 * p;
                ll y1 = k1 * p;
                if (k0 != n) {
                tmp = min(tmp, (u128)(n - y0) * D + A[i] + f(k0));
                }
                if (k1 != n) {
                    tmp = min(tmp, (u128)(y1 - n) * D + A[i] + f(k1));
                }
            }
            return m[n] = tmp;
        };

        cout << (ll)f(N) << endl;
    }

    return 0;
}
