#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <cmath>
#include <map>
#include <tuple>
#include <queue>
#include <stack>
#include <iomanip>

#define MOD (1000000007)
using namespace std;

typedef long long ll;

typedef tuple<ll, ll> tup; // mp, tairyoku

// int main() {
//     auto compare = [](int a, int b) {
//       return a < b;
//     };

//     std::priority_queue<
//       int,
//       std::vector<int>,
//       decltype(compare) // 比較関数オブジェクトを指定
//     > que {compare};

//     que.push(3);
//     que.push(1);
//     que.push(4);
// }

auto compare = [](tup a, tup b) {
    ll a_mp = get<0>(a);
    ll b_mp = get<0>(b);
    return a_mp < b_mp;
    // if (a_mp != b_mp) return a_mp > b_mp;
    // else return get<0>(a) > get<0>(b);
};

map<ll, ll> m;
void push_el(priority_queue<tup, vector<tup>, decltype(compare)> &q, ll num, ll coin) {
    auto itr = m.find(num);

    if (num < 0) return;
    if(m.find(0) != m.end() && coin >= m[0]) {
        return;
    }
    // cout << "stacked: " ;
    if(itr == m.end()|| m[num] > coin) {
        m[num] = coin;
       // cout << "stacked: " << num << "-" << coin << "-" << endl;;
        q.push(make_tuple( num , coin));
    }
}

// bool operator< (const tup &tup1, const tup &tup2){
//     return  get<1>(tup1) <  get<1>(tup2);
// };


int main() {
    ll T;
    cin >> T;
    for(int cnt = 0; cnt < T; cnt++ ) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;

        // cout << N << endl;
        m.clear();

        // vector<ll> sorted_v({A,B,C,D});
        // sort(sorted_v.begin(), sorted_v.end());

        priority_queue<tup, vector<tup>, decltype(compare)> q {compare};

        ll min_coin = -1;
        ll min_coin_theory= min({ N*D}); //60*(A+D)
        //cout << min_coin_theory << endl;
        q.push(make_tuple(N, 0));
        while(q.size() >= 1) {
            //cout << "***********************" << endl;
            tup el = q.top();q.pop();
            ll num = get<0>(el);
            ll coin = get<1>(el);

            //cout << num << ":" << coin << ":" << endl;

            //if(coin >= min_coin_theory + 1) continue;
            if(num == 0) {
                if(coin < 0) continue;
                if(min_coin < 0) min_coin = coin;
                else min_coin = min(coin, min_coin);
                continue;
            }

            // if(num > 0 && (min_coin_theory - coin) / D > num )  push_el(q, 0, coin + num* D);
            if(num > 0 && 2e18 / D >= num )  push_el(q, 0, coin + num* D);
            if(num % 2 == 0) push_el(q, num / 2, min({coin + A}));
            if(num % 2 == 1 && num != 1) {
                push_el(q, (num - 1) / 2, min({coin + A + D}));
                push_el(q, (num + 1) / 2, min({coin + A + D}));
            }
            if(num % 3 == 0) push_el(q, num / 3, min({coin + B}));
            if(num % 3 == 1 && num != 1) {
                push_el(q, (num - 1) / 3, min({coin + B + D}));
                push_el(q, (num + 2) / 3, min({coin + B + (2 * D)}));
            }
            if(num % 3 == 2 && num != 2) {
                push_el(q, (num - 2) / 3, min({coin + B + (2* D)}));
                push_el(q, (num + 1) / 3, min({coin + B +  D}));
            }
            if(num % 5 == 0) push_el(q, num / 5, min({coin + C}));
            if(num % 5 == 1 && num != 1) {
                push_el(q, (num - 1) / 5, min({coin + C + D}));
                push_el(q, (num + 4) / 5, min({coin + C + (4 * D)}));
            }
            if(num % 5 == 2 && num != 2) {
                push_el(q, (num - 2) / 5, min({coin + C + (2 * D)}));
                push_el(q, (num + 3) / 5, min({coin + C + (3 * D) }));
            }
            if(num % 5 == 3 && num != 3) {
                push_el(q, (num - 3) / 5, min({coin + C + (3 * D)}));
                push_el(q, (num + 2) / 5, min({coin + C + (2 * D) }));
            }
            if(num % 5 == 4 && num != 4) {
                push_el(q, (num - 4) / 5, min({coin + C + (4 * D) }));
                push_el(q, (num + 1) / 5, min({coin + C +  D}));
            }
        }
        cout << min_coin << endl;
    }


    return 0;
}


Measured memory_bytes: 4716