#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#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);
    }
};

struct safe_array_hash {
    template<typename T_array>
    uint64_t operator()(const T_array &arr) const {
        static const uint64_t RANDOM_MULT = safe_hash::splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)) | 1;
        static safe_hash hash_obj;
        uint64_t hash_key = 0;

        for (const auto &x : arr)
            hash_key = RANDOM_MULT * hash_key + x;

        return hash_obj(hash_key);
    }
};


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

int64_t N, A, B, C, D;
unordered_map<array<int, 4>, int64_t, safe_array_hash> save;

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 solve(int a, int b, int c, int up) {
    int64_t n = evaluate(a, b, c);
    int64_t n_with = n + up;

    if (n_with == 0)
        return 0;

    if (n_with == 1)
        return D;

    array<int, 4> key = {a, b, c, up};

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

    int64_t ans = (long double) D * n_with < 1e18 ? D * n_with : INF64;
    ans = min(ans, D * (n_with % 2) + A + solve(a + 1, b, c, n_with / 2 > evaluate(a + 1, b, c)));
    ans = min(ans, D * (n_with % 3) + B + solve(a, b + 1, c, n_with / 3 > evaluate(a, b + 1, c)));
    ans = min(ans, D * (n_with % 5) + C + solve(a, b, c + 1, n_with / 5 > evaluate(a, b, c + 1)));
    ans = min(ans, (2 - n_with % 2) * D + A + solve(a + 1, b, c, true));
    ans = min(ans, (3 - n_with % 3) * D + B + solve(a, b + 1, c, true));
    ans = min(ans, (5 - n_with % 5) * D + C + solve(a, b, c + 1, true));
    dbg(a, b, c, up, ans);
    return save[key] = ans;
}

void run_case() {
    cin >> N >> A >> B >> C >> D;
    save.clear();
    int64_t answer = int64_t(solve(0, 0, 0, false));
    cout << answer << '\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: 4600