#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


    auto calc = [&](long long n, long long a, long long b, long long c, long long d) {
        const int N = 100100;
        const long long INF = 1LL << 62;
        vector<long long> dp(N + 1, INF);
        dp[0] = 0;
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
        pq.emplace(0, 0);

        vector<long long> costs(10, 0);
        costs[2] = a;
        costs[3] = b;
        costs[5] = c;
        costs[1] = d;
        while (!pq.empty()) {
            long long x = pq.top().second;
            long long d = pq.top().first;
            pq.pop();
            // cout << x << " " << d << endl;
            if (d != dp[x]) {
                continue;
            }
            {
                for (auto p : {2, 3, 5}) {
                    long long nx = x * p;
                    if (nx <= N) {
                        if (dp[nx] > d + costs[p]) {
                            dp[nx] = d + costs[p];
                            pq.emplace(dp[nx], nx);
                        }
                    } else {
                        break;
                    }
                }
            }
            {
                for (int i = -1; i < 2; i += 2) {
                    long long nx = x + i;
                    if (nx > 0 && nx <= N) {
                        if (dp[nx] > d + costs[1]) {
                            dp[nx] = d + costs[1];
                            pq.emplace(dp[nx], nx);
                        }
                    }
                }
            }
        }

        vector<long long> mins(10, 0);
        for (auto x : {2, 3, 5}) {
            long long d = (costs[1] * (x - 1));
            mins[x] = (costs[x] + d - 1) / d;
        }
        map<long long, long long> M;
        M[0] = 0;
        function<long long(long long)> dfs = [&](long long x) -> long long {
            if (x <= N / 10) {
                return dp[x];
            }
            if (M.count(x) != 0) {
                return M[x];
            }
            auto& ans = M[x];
            ans = INF;
            if (x < INF / costs[1]) {
                ans = x * costs[1];
            }
            for (auto p : {2, 3, 5})
            {
                for (auto d : {x % p, x % p - p}) {
                    auto nx = x - d;
                    assert(nx % p == 0);
                    long long w = abs(x - nx) * costs[1];
                    if (nx > 0) {
                        ans = min(ans, w + dfs(nx / p) + (nx >= mins[p] * p ? costs[p] : nx / p * (p - 1) * costs[1]));
                        // ans = min(ans, w + dfs(nx / p) + costs[p]);
                    }
                }
            } 
            // {
            //     ans = min(ans, dfs(x / 3) + (x >= mins[3] ? costs[3] : x *  costs[1]);
            // }
            // {
            //    ans = min(ans, dfs(x / 5) + (x >= mins[5] ? costs[5] : x * costs[1]);
            // }
            // cout << x << " " << ans << endl;
            return ans;
        };

        return dfs(n);
    };

    int t;
    cin >> t;
    while (t-- > 0) {
        long long n;
        long long a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        cout << calc(n, a, b, c, d) << '\n';
    }

    return 0;
}

Measured memory_bytes: 7900