#include <bits/stdc++.h>

// #define DEBUG 1

#define int long long
#define for0(i,n) for (int i=0; i<n; i++)
#define fill1(a,z) fill_n(a, sizeof(a)/sizeof(a[0]), z)
#define fill2(a,z) fill_n(a[0], sizeof(a)/sizeof(a[0][0]), z)
#define fill3(a,z) fill_n(a[0][0], sizeof(a)/sizeof(a[0][0][0]), z)
#define mp make_pair
#define X first
#define Y second
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define pmod(x,m) (((x)%(m)+m)%m)
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define priter(v) {for (auto x : v) {pr(x)} nl}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define priter(v)
#define debug
#endif
#define MAXN 100000

using namespace std;

typedef unsigned long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

unordered_map<ll,ll> memo;

ll solve(ll N, ll A, ll B, ll C, ll D) {
    assert(N > 0);
    if (N == 1)
        return D;
    else if (memo.find(N) != memo.end())
        return memo[N];
    
    // cout << "solve " << N << endl;
    ll best = INFL;
    if (N <= INFL/D)
        best = N*D;
    
    if (N%2 == 0) {
        ll res = solve(N/2, A, B, C, D) + A;
        best = min(best, res);
    }
    else {
        ll res = solve((N+1)/2, A, B, C, D) + A + D;
        best = min(best, res);
        res = solve((N-1)/2, A, B, C, D) + A + D;
        best = min(best, res);
    }
    if (N >= 3) {
        if (N%3 == 0) {
            ll res = solve(N/3, A, B, C, D) + B;
            best = min(best, res);
        }
        else if ((N-1)%3 == 0) {
            ll res = solve((N-1)/3, A, B, C, D) + B + D;
            best = min(best, res);        
        }
        else if ((N+1)%3 == 0) {
            ll res = solve((N+1)/3, A, B, C, D) + B + D;
            best = min(best, res);        
        }
    }
    if (N >= 4) {
        if (N%5 == 0) {
            ll res = solve(N/5, A, B, C, D) + C;
            best = min(best, res);
        }
        else if ((N-1)%5 == 0) {
            ll res = solve((N-1)/5, A, B, C, D) + C + D;
            best = min(best, res);        
        }
        else if ((N+1)%5 == 0) {
            ll res = solve((N+1)/5, A, B, C, D) + C + D;
            best = min(best, res);        
        }
        else if ((N-2)%5 == 0) {
            ll res = solve((N-2)/5, A, B, C, D) + C + D + D;
            best = min(best, res);        
        }
        else if ((N+2)%5 == 0) {
            ll res = solve((N+2)/5, A, B, C, D) + C + D + D;
            best = min(best, res);        
        }
    }
    
    memo[N] = best;
    return best;
}

int32_t main()
{
    #ifdef DEBUG
    //freopen("A.txt","r",stdin);
    //freopen("","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int cases;
    cin >> cases;
    for0(casen,cases) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;
        memo.clear();
        ll ans = solve(N, A, B, C, D);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4116