#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

ll choice_3(ll N,ll b,ll d) {
    ll amari = N%3;
    if (amari == 2) amari -= 3; //amari = {-1,0,1}
    ll cost = d*abs(amari) + b;
    ll next = (N - amari) / 3;
    double index = double (cost)/d;
    if (index > N - next) return(min(cost,(N-next)*d));
    else return(cost);
}

ll choice_5(ll N,ll c,ll d) {
    ll amari = N%5;
    if (amari >= 3) amari -= 5;
    ll cost = d*abs(amari) + c;
    ll next = (N - amari) /5;
    double index = double (cost)/d;
    if (index > N - next) return(min(cost,(N-next)*d));
    else return(cost);
}

ll choice_2_1(ll N,ll a,ll d) {
    ll amari = N%2;
    ll cost = d*amari + a;
    ll next = (N - amari) / 2;
    double index = double (cost)/d;
    if (index > N - next) return(min(cost,(N-next)*d));
    else return(cost);
}

ll choice_2_2(ll N,ll a,ll d) {
    ll amari = N%2;
    ll cost = d*amari + a;
    ll next = (N + amari) / 2;
    double index = double (cost)/d;
    if (index > N - next) return(min(cost,(N-next)*d));
    else return(cost);
}



ll choice_cost(ll i,ll N,ll a,ll b,ll c,ll d) { //return コスト
    if (i == 0) return(choice_3(N,b,d));
    if (i == 1) return(choice_5(N,c,d));
    if (i == 2) return(choice_2_1(N,a,d));
    if (i == 3) return(choice_2_2(N,a,d));
}


ll choice_3_num(ll N,ll b,ll d) {
    ll amari = N%3;
    if (amari == 2) amari -= 3; //amari = {-1,0,1}
    ll cost = d*abs(amari) + b;
    ll next = (N - amari) / 3;
    return (next); 
}

ll choice_5_num(ll N,ll c,ll d) {
    ll amari = N%5;
    if (amari >= 3) amari -= 5;
    ll cost = d*abs(amari) + c;
    ll next = (N - amari) /5;
    return (next);
}

ll choice_2_1_num(ll N,ll a,ll d) {
    ll amari = N%2;
    ll cost = d*amari + a;
    ll next = (N - amari) / 2;
    return (next);
}

ll choice_2_2_num(ll N,ll a,ll d) {
    ll amari = N%2;
    ll cost = d*amari + a;
    ll next = (N + amari) / 2;
    return (next);
}

ll choice_number(ll i,ll N,ll a,ll b,ll c,ll d) { //return コスト
    if (i == 0) return(choice_3_num(N,b,d));
    if (i == 1) return(choice_5_num(N,c,d));
    if (i == 2) return(choice_2_1_num(N,a,d));
    if (i == 3) return(choice_2_2_num(N,a,d));
}



ll solve(ll N,ll a,ll b,ll c,ll d) {
    map<ll,ll> seen; //その数字からの遷移をみたか？
    priority_queue<long long> pq; //次に遷移を見る数
    pq.push(N); //初期値
    map<ll,ll> mp; //cost保存
    mp[N] = 0; //Nはコスト０
    while(!pq.empty()) {
        //cout << 111 << endl;
        ll next = pq.top(); //今回遷移を考えるスタートの数字
        pq.pop();
        if (seen[next] == 111) continue; //既に見てたら飛ばす
        seen[next] = 111; //nextからの遷移を見たことを保存
        for (ll i = 0;i<4;i++) {  //4パターンの遷移
            ll next_choice = choice_number(i,next,a,b,c,d);
            pq.push(next_choice);  //結果の数追加
            if (mp[next_choice] == 0) mp[next_choice] = mp[next] + choice_cost(i,next,a,b,c,d); //初見
            else chmin(mp[next_choice],mp[next] + choice_cost(i,next,a,b,c,d)); //costの更新
        }
    }
    return(mp[0]);
    
}
int main() {
    ll T;
    cin >> T;
    for (ll i = 0;i<T;i++) {
        ll N,a,b,c,d;
        cin >> N >> a >> b >> c >> d;
        cout << solve(N,a,b,c,d) << endl;
    }
}

Measured memory_bytes: 5240