#include <bits/stdc++.h>

using namespace std;

const int max_x = 100;
const int shift = max_x / 2;
const long long inf = 5000111222000111222LL;
constexpr int val[3] = {2, 3, 5};
constexpr int mx_p[3] = {65, 45, 33};

int t, num[mx_p[0]][mx_p[1]][mx_p[2]];
long long n, a[3], d;
vector<long long> pw[3];
long long dp[13111][max_x];

long long mul(long long x, long long y) {
    if (!x || !y) {
        return 0;
    }
    if (x > inf / y) {
        return inf;
    }
    return x * y;
}

void upd(int i, int x, long long val) {
    if (dp[i][x] == -1) {
        dp[i][x] = val;
    } else {
        dp[i][x] = min(dp[i][x], val);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    for (int i = 0; i < 3; ++i) {
        pw[i].push_back(1);
        while (mul(val[i], pw[i].back()) < inf) {
            pw[i].push_back(pw[i].back() * val[i]);
        }
        //cout << pw[i].size() << endl;
    }
    vector<int> ids[3];
    vector<long long> vals;
    memset(num, -1, sizeof(num));
    for (int i = 0; i < pw[0].size(); ++i) {
        for (int j = 0; j < pw[1].size(); ++j) {
            for (int k = 0; k < pw[2].size(); ++k) {
                long long val = mul(pw[0][i], mul(pw[1][j], pw[2][k]));
                if (val < inf) {
                    num[i][j][k] = ids[0].size();
                    ids[0].push_back(i);
                    ids[1].push_back(j);
                    ids[2].push_back(k);
                    vals.push_back(val);
                }
            }
        }
    }
    //cout << ids[0].size() << endl;
    cin >> t;
    while (t--) {
        cin >> n >> a[0] >> a[1] >> a[2] >> d;
        assert(n <= 1000000000000000000LL);
        memset(dp, -1, sizeof(dp));
        dp[num[0][0][0]][shift] = 0;
        long long ans = inf;
        for (int i = 0; i < ids[0].size(); ++i) {
            for (int x = 0; x + 1 < max_x; ++x) {
                if (dp[i][x] == -1) {
                    continue;
                }
                upd(i, x + 1, dp[i][x] + d);
            }
            for (int x = max_x - 1; x; --x) {
                if (dp[i][x] == -1) {
                    continue;
                }
                upd(i, x - 1, dp[i][x] + d);
            }
            for (int x = 0; x < max_x; ++x) {
                if (dp[i][x] == -1) {
                    continue;
                }
                long long cur = n / vals[i] + x - shift;
                if (cur < 0) {
                    continue;
                }
                ans = min(ans, dp[i][x] + mul(cur, d));
                for (int j = 0; j < 3; ++j) {
                    if (cur % val[j]) {
                        continue;
                    }
                    const int to = num[ids[0][i] + (j == 0)][ids[1][i] + (j == 1)][ids[2][i] + (j == 2)];
                    if (to == -1) {
                        continue;
                    }
                    long long tox = cur / val[j] + shift - n / vals[to];
                    if (0 <= tox && tox < max_x) {
                        upd(to, tox, dp[i][x] + a[j]);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 14400