#include <iostream>
#include <map>
#include <algorithm>

long long N, A, B, C, D;
std::map<long long, long long> m;

long long cost(long long n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return D;
    } else if (m.count(n)) {
        return m[n];
    }

    m[n] = std::min({
        n % 2 * D + A + cost(n / 2),
        (2 - n % 2) % 2 * D + A + cost((n + 1) / 2),
        n % 3 * D + B + cost(n / 3),
        (3 - n % 3) % 3 * D + B + cost((n + 2) / 3),
        n % 5 * D + C + cost(n / 5),
        (5 - n % 5) % 5 * D + C + cost((n + 4) / 5),
        n * D > 0 ? n * D : 1LL << 60,
    });

    return m[n];
}

int main() {
    int T;
    std::cin >> T;

    for (int i = 0; i < T; i++) {
        std::cin >> N >> A >> B >> C >> D;
        m.clear();
        std::cout << cost(N) << "\n";
    }
}