#include <bits/stdc++.h>

inline long long read() {
    char c; long long x; for (c = getchar(); !isdigit(c); c = getchar());
    for (x = 0; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } return x;
}

const int N = 5e6 + 5, V = 1e7 + 5;

long long n, ans, dis[N];
int a, b, c, d, m, tag[V];
std::map<long long, int> map;
std::vector<std::pair<int, long long>> e[N];

int get(long long n) {
    if (n < V) {
        return tag[n];
    } else {
        if (!map.count(n)) {
            return -1;
        } else {
            return map[n];
        }
    }
}
int add(long long n) {
    if (n < V) {
        return tag[n] = m++;
    } else {
        return map[n] = m++;
    }
}

int build(long long n) {
    int u = get(n);
    if (u != -1) { return u; }
    u = add(n);
    if (n % 2 == 0) {
        e[build(n / 2)].push_back({u, std::min(0ll + a, std::min(n / 2ll, (long long) 2e9) * d)});
    } else {
        e[build((n - 1) / 2)].push_back({u, d + std::min(0ll + a, std::min(n / 2ll, (long long) 2e9) * d)});
        e[build((n + 1) / 2)].push_back({u, d + a});
    }
    if (n % 3 == 0) {
        e[build(n / 3)].push_back({u, std::min(0ll + b, std::min(n / 3ll * 2, (long long) 2e9) * d)});
    } else if (n % 3 == 1) {
        e[build((n - 1) / 3)].push_back({u, d + std::min(0ll + b, std::min(n / 3ll * 2, (long long) 2e9) * d)});
        e[build((n + 2) / 3)].push_back({u, d * 2ll + b});
    } else {
        e[build((n - 2) / 3)].push_back({u, d * 2 + std::min(0ll + b, std::min(n / 3ll * 2, (long long) 2e9) * d)});
        e[build((n + 1) / 3)].push_back({u, d + b});
    }
    if (n % 5 == 0) {
        e[build(n / 5)].push_back({u, std::min(0ll + c, std::min(n / 5ll * 4, (long long) 2e9) * d)});
    } else if (n % 5 == 1) {
        e[build((n - 1) / 5)].push_back({u, d + std::min(0ll + c, std::min(n / 5ll * 4, (long long) 2e9) * d)});
        e[build((n + 4) / 5)].push_back({u, d * 4ll + c});
    } else if (n % 5 == 2) {
        e[build((n - 2) / 5)].push_back({u, d * 2 + std::min(0ll + c, std::min(n / 5ll * 4, (long long) 2e9) * d)});
        e[build((n + 3) / 5)].push_back({u, d * 3ll + c});
    } else if (n % 5 == 3) {
        e[build((n - 3) / 5)].push_back({u, d * 3ll + std::min(0ll + c, std::min(n / 5ll * 4, (long long) 2e9) * d)});
        e[build((n + 2) / 5)].push_back({u, d * 2ll + c});
    } else {
        e[build((n - 4) / 5)].push_back({u, d * 4ll + std::min(0ll + c, std::min(n / 5ll * 4, (long long) 2e9) * d)});
        e[build((n + 1) / 5)].push_back({u, d + c});
    }
    return u;
}

void dijkstra(int s) {
    int t = map[n];
    for (int u = 0; u < m; u++) { dis[u] = 5e18; }
    dis[s] = 0;
    std::priority_queue<std::pair<long long, int>> que;
    for (que.push({0, s}); !que.empty(); ) {
        int u = que.top().second;
        long long d = -que.top().first;
        que.pop();
        if (d != dis[u]) { continue; }
        if (u == t) { return; }
        for (auto i : e[u]) {
            int v = i.first;
            long long w = i.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                que.push({-dis[v], v});
            }
        }
    }
}

int main() {
    for (int T = read(); T; T--) {
        for (int i = 0; i < V; i++) { tag[i] = -1; }
        n = read(); a = read(); b = read(); c = read(); d = read();
        m = 0;
        map.clear();
        build(n);
        dijkstra(get(0));
        printf("%lld\n", dis[get(n)]);
        for (int u = 0; u < m; u++) { e[u].clear(); }
    }
    return 0;
}

Measured memory_bytes: 162176