#include "bits/stdc++.h"

using namespace std;

long long minCoin(long long currN, long long A, long long B, long long C, long long D, map<long long, long long>& memo) {
    if (currN == 0) {
        return 0LL;
    }
    if (currN == 1) {
        return D;
    }

    if (memo.count(currN) > 0) {
        return memo[currN];
    }

    long long div2;
    if (currN % 2 == 0) {
        div2 = A + minCoin(currN / 2, A, B, C, D, memo);
    }
    else {
        if (currN - 1 < 0) {
            div2 = A + D + minCoin((currN + 1) / 2, A, B, C, D, memo);
        }
        else {
            div2 = min(
                A + D + minCoin((currN - 1) / 2, A, B, C, D, memo)
                , A + D + minCoin((currN + 1) / 2, A, B, C, D, memo)
            );
        }
    }

    long long res3 = currN % 3;
    long long div3;
    if (res3 == 0) {
        div3 = B + minCoin(currN / 3, A, B, C, D, memo);
    }
    else if (res3 == 1) {
        if (currN - 1 < 0) {
            div3 = B + 2 * D + minCoin((currN + 2) / 3, A, B, C, D, memo);
        }
        else {
            div3 = min(
                B + D + minCoin((currN - 1) / 3, A, B, C, D, memo)
                , B + 2 * D + minCoin((currN + 2) / 3, A, B, C, D, memo)
            );
        }
    }
    else {
        if (currN - 2 < 0) {
            div3 = B + D + minCoin((currN + 1) / 3, A, B, C, D, memo);
        }
        else {
            div3 = min(
                B + 2 * D + minCoin((currN - 2) / 3, A, B, C, D, memo)
                , B + D + minCoin((currN + 1) / 3, A, B, C, D, memo)
            );
        }
    }

    long long res5 = currN % 5;
    long long div5;
    if (res5 == 0) {
        div5 = C + minCoin(currN / 5, A, B, C, D, memo);
    }
    else if (res5 == 1) {
        if (currN - 1 < 0) {
            div5 = C + 4 * D + minCoin((currN + 4) / 5, A, B, C, D, memo);
        }
        else {
            div5 = min(
                C + D + minCoin((currN - 1) / 5, A, B, C, D, memo)
                , C + 4 * D + minCoin((currN + 4) / 5, A, B, C, D, memo)
            );
        }
    }
    else if (res5 == 2) {
        if (currN - 2 < 0) {
            div5 = C + 3 * D + minCoin((currN + 3) / 5, A, B, C, D, memo);
        }
        else {
            div5 = min(
                C + 2 * D + minCoin((currN - 2) / 5, A, B, C, D, memo)
                , C + 3 * D + minCoin((currN + 3) / 5, A, B, C, D, memo)
            );
        }
    }
    else if (res5 == 3) {
        if (currN - 3 < 0) {
            div5 = C + 2 * D + minCoin((currN + 2) / 5, A, B, C, D, memo);
        }
        else {
            div5 = min(
                C + 3 * D + minCoin((currN - 3) / 5, A, B, C, D, memo)
                , C + 2 * D + minCoin((currN + 2) / 5, A, B, C, D, memo)
            );
        }
    }
    else {
        if (currN - 4 < 0) {
            div5 = C + D + minCoin((currN + 1) / 5, A, B, C, D, memo);
        }
        else {
            div5 = min(
                C + 4 * D + minCoin((currN - 4) / 5, A, B, C, D, memo)
                , C + D + minCoin((currN + 1) / 5, A, B, C, D, memo)
            );
        }
    }

    long long nodiv = currN * D;

    long long ans = nodiv > 0 ? min(min(min(div2, div3), div5), nodiv) : min(min(div2, div3), div5);
    memo.insert(make_pair(currN, ans));
    return ans;
}

void Main() {
    long long T;
    cin >> T;
    vector<long long> N(T, 0), A(T, 0), B(T, 0), C(T, 0), D(T, 0);
    for (long long i = 0; i < T; ++i) {
        cin >> N[i] >> A[i] >> B[i] >> C[i] >> D[i];
    }

    for (long long i = 0; i < T; ++i) {
        map<long long, long long> memo;
        long long ans = minCoin(N[i], A[i], B[i], C[i], D[i], memo);
        cout << ans << endl;
    }
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4468