#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };

struct safe_hash {
    static unsigned hash32(unsigned x) {
        x = (x ^ (x >> 16)) * 0x45d9f3b;
        x = (x ^ (x >> 16)) * 0x45d9f3b;
        return x ^ (x >> 16);
    }

    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    template<typename T>
    uint64_t operator()(T x) const {
        static const uint64_t FIXED_RANDOM = splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
        return sizeof(x) <= 4 ? hash32(x ^ unsigned(FIXED_RANDOM)) : splitmix64(x ^ FIXED_RANDOM);
    }
};


const int64_t INF64 = int64_t(2e18) + 5;

int64_t N, A, B, C, D;
unordered_map<int64_t, int64_t, safe_hash> save;
set<int64_t> divisions;

int64_t evaluate(int a, int b, int c) {
    int64_t n = N;
    while (a-- > 0) n /= 2;
    while (b-- > 0) n /= 3;
    while (c-- > 0) n /= 5;
    return n;
}

int64_t closest(int64_t n) {
    int64_t dist = INF64;
    auto it = divisions.lower_bound(n);

    if (it != divisions.end())
        dist = min(dist, *it - n);

    if (it != divisions.begin()) {
        it--;
        dist = min(dist, n - *it);
    }

    return dist;
}

const int CUTOFF = 10;

int64_t solve(int64_t n) {
    if (n == 0)
        return 0;

    if (n == 1)
        return D;

    if (closest(n) > CUTOFF)
        return INF64;

    if (save.find(n) != save.end())
        return save[n];

    int64_t ans = (long double) D * n < INF64 ? D * n : INF64;
    ans = min(ans, n % 2 * D + A + solve(n / 2));
    ans = min(ans, n % 3 * D + B + solve(n / 3));
    ans = min(ans, n % 5 * D + C + solve(n / 5));
    if (n > 2) ans = min(ans, (2 - n % 2) * D + A + solve(n / 2 + 1));
    ans = min(ans, (3 - n % 3) * D + B + solve(n / 3 + 1));
    ans = min(ans, (5 - n % 5) * D + C + solve(n / 5 + 1));
    return save[n] = ans;
}

void run_case() {
    cin >> N >> A >> B >> C >> D;
    save.clear();

    for (int a = 0; a <= 60; a++)
        for (int b = 0; b <= 40; b++)
            for (int c = 0; c <= 30; c++)
                divisions.insert(evaluate(a, b, c));

    cout << solve(N) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int tests;
    cin >> tests;

    while (tests-- > 0)
        run_case();
}


Measured memory_bytes: 4900