#include <bits/stdc++.h>
using namespace std;
#define FIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef long long unsigned lu;
typedef long double ld;
typedef std::pair<int, int> ii;
typedef std::pair<int, ii> iii;
typedef std::pair<ll, ll> ll2;
typedef std::pair<ll, ll2> ll3;
typedef std::pair<double, double> dd;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<string> vs;

template<class T> using min_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T> using max_queue = priority_queue<T>;

#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define bg begin()

template<class A, class B> ostream& operator << (ostream& out, const pair<A, B>& a) {
    return out << "(" << a.first << ", " << a.second << ") ";
}
template<class T, size_t... I> void print_tuple(ostream& s, T const& a, index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0? "" : ", ") << get<I>(a)), 0)...};
}
template<class... A> ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '('; print_tuple(s, a, index_sequence_for<A...>{}); return s << ')';
}
template<class T> ostream& print_collection(ostream& out, T const& a) {
    out << "{ "; for (auto& i : a) out << i << " "; return out << " } ";
}
template<class A> ostream& operator << (ostream& out, const vector<A>& a) {
    out << "[ "; for(int i=0; i < a.size(); ++i) out << "(" << i << " , " << a[i] << ") "; out << " ] ";
    return out;
}
template<class T> ostream& operator<<(ostream& s, queue<T> const& a) { return print_collection(s, a); }
template<class T> ostream& operator<<(ostream& s, stack<T> const& a) { return print_collection(s, a); }
template<class T> ostream& operator<<(ostream& s, priority_queue<T> const& a) { return print_collection(s, a); }
template<class T, class U> ostream& operator<<(ostream& s, multimap<T, U> const& a) { return print_collection(s, a); }
template<class T> ostream& operator<<(ostream& s, multiset<T> const& a) { return print_collection(s, a); }
template<class T, class U> ostream& operator<<(ostream& s, map<T, U> const& a) { return print_collection(s, a); }
template<class T> ostream& operator<<(ostream& s, set<T> const& a) { return print_collection(s, a); }
template<class T, class U> ostream& operator<<(ostream& s, unordered_map<T, U> const& a) { return print_collection(s, a); }
template<class T> ostream& operator<<(ostream& s, unordered_set<T> const& a) { return print_collection(s, a); }

void solve() {
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;

    min_queue<ll2> pq; // cost, number reached
    pq.push({0, N});
    
    unordered_set<ll> visited;
    ll ans = 1e18;
    
    while(pq.top().se != 0 && pq.top().fi < ans) {
        // cout << pq.top() << endl;
        ll cost = pq.top().fi;
        ll n = pq.top().se;
        pq.pop();

        if (visited.find(n) != visited.end()) continue;
        visited.insert(n);
        
        if (n <= ans/D) ans = min(ans, cost+n*D); // to avoid overflow check n*D < ans which is our upper bound from the statement!

        if (n % 2 == 0) pq.push({cost+A, n/2});
        else {
            pq.push({cost+A+D, (n+1)/2});
            pq.push({cost+A+D, (n-1)/2});
        }
        if (n % 3 == 0) pq.push({cost+B, n/3});
        else {
            if (n % 3 == 1) pq.push({cost+B+D, (n-1)/3});
            else pq.push({cost+B+D, (n+1)/3});
        }
        if (n % 5 == 0) pq.push({cost+C, n/5});
        else {
            int r = n % 5;
            if (r <= 2) pq.push({cost+C+D*r, (n-r)/5});
            else pq.push({cost+C+D*(5-r), (n+5-r)/5});
        }
    }

    cout << min(ans, pq.top().fi) << "\n";
}

int main () {
    FIO();
    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4084