/*
Author : Hocky Yudhiono
5/23/2020 7:01:02 PM

1. You can sort the query if offline!
2. Don't bring the dp remaining state when dfsing on DP on Tree.
3. Try to reverse (Think from the back) if you stuck.
4. Be careful when submitting Div. 2 D-F, dont waste it on stupid WAs.
5. Try to reduce a problem
*/

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <limits>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

typedef long long LL;
typedef long long ll;
typedef long double LD;
typedef vector<int> vi;
typedef pair<LL,LL> PLL;
typedef pair<LL,int> PLI;
typedef pair<int,int> PII;
typedef pair<int,int> pii;
typedef vector<vector<LL>> VVL;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define mp make_pair
#define pb push_back
#define remove erase
#define fi first
#define se second

//If the time limit is strict, try not to use long double

//Remember to undefine if the problem is interactive
#define endl '\n'
#define DEBUG(X) cout << ">>> DEBUG(" << __LINE__ << ") " << #X << " = " << (X) << endl

const double EPS = 1e-9;
const int INFMEM = 63;
const int INF = 1061109567;
const LL LINF = 4557430888798830399LL;
const double DINF = numeric_limits<double>::infinity();
const LL MOD = 1000000007;
const int dx[8] = {0,0,1,-1,1,-1,1,-1};
const int dy[8] = {1,-1,0,0,1,-1,-1,1};
// Do dir^1 to get reverse direction
const char dch[4] = {'R','L','D','U'};
// const string ds[8] = {"E","W","S","N","SE","NW","SW","NE"};
const double PI = 3.141592653589793;

inline void open(string a){
    freopen((a+".in").c_str(),"r",stdin);
    freopen((a+".out").c_str(),"w",stdout);
}

inline void fasterios(){
    //Do not use if interactive
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

LL n;
struct dt{
    LL pos,step;
    bool operator<(const dt &other)const{
        if(step != other.step) return step > other.step;
        return pos < other.pos;
    }
};
priority_queue <dt> antri;
LL go[] = {2,3,5};
LL cost[3];
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL d,ans;
#include <unordered_map>
#include <unordered_set>
unordered_map<LL, LL, custom_hash> dist;
void dijk(dt now){
    if(dist.count(now.pos) && now.step > dist[now.pos]) return;
    if(now.pos == 0) return;
    if(now.pos <= (1000000000000000000LL-now.step)/d) ans = min(ans,now.step+now.pos*d);
    // cout << now.pos << " " << now.step << endl;
    for(int i = 0;i < 3;i++){
        LL need = now.pos%go[i];
        {
            LL nx = now.pos/go[i]; nx++;
            LL nxstep = now.step+((go[i]-need)*d)+cost[i];
            if(!(dist.count(nx) && nxstep >= dist[nx])){
                dist[nx] = nxstep;
                antri.push({nx,nxstep});
            }
        }
        {
            LL nx = now.pos/go[i];
            LL nxstep = now.step+(need*d)+(now.pos-need == 0 ? 0 : cost[i]);
            if(!(dist.count(nx) && nxstep >= dist[nx])){
                dist[nx] = nxstep;
                antri.push({nx,nxstep});
            }
        }
    }
}

int main(){
    fasterios();
    int testCases; cin >> testCases; int tc = 0;
    while(++tc <= testCases){
        // cout << "Case #" << tc << ": ";
        //reset
        dist.clear();
        ans = LINF;
        //compute
        cin >> n >> cost[0] >> cost[1] >> cost[2] >> d;
        antri.push({n,0});
        while(!antri.empty()){
            dt tmp = antri.top();
            antri.pop();
            dijk(tmp);
        }
        ans = min(ans,dist[0]);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4712