#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P     = pair<ll, ll>;
const ll mod= 1e9 + 7;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll(i)= 0; (i) < (n); (i)++)
#define REPS(i, n) for(ll(i)= 1; (i) <= (n); (i)++)
#define RREP(i, n) for(ll(i)= (n - 1); (i) >= 0; (i)--)
#define RREPS(i, n) for(ll(i)= (n); (i) > 0; (i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());

template <class T>
inline void chmin(T& a, T b) {
    if(a > b) { a= b; }
}

template <class T>
inline void chmax(T& a, T b) {
    if(a < b) { a= b; }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    ll T;
    cin >> T;
    REP(kjhasrkfhjasdf, T) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;
        map<ll, ll> nums;
        nums[N]= 0;
        while(1){
            if(nums.size() == 1 && nums.count(1)) { break; }
            ll ind = (*nums.rbegin()).F;
            ll cost= (*nums.rbegin()).S;
            nums.erase(--nums.end());
            if(ind > (ind + 1) / 2 && (ind + 1) / 2 > 0) {
                if((ind - (ind + 1) / 2) >= (A + (ind % 2) * D) / D) {
                    if(nums.count((ind + 1) / 2)) {
                        chmin(nums[(ind + 1) / 2], cost + A + (ind % 2) * D);
                    } else {
                        nums[(ind + 1) / 2]= cost + A + (ind % 2) * D;
                    }
                } else {
                    if(nums.count((ind + 1) / 2)) {
                        chmin(nums[(ind + 1) / 2],
                              min(cost + A + (ind % 2) * D,
                                  cost + (ind - (ind + 1) / 2) * D));
                    } else {
                        nums[(ind + 1) / 2]=
                            min(cost + A + (ind % 2) * D,
                                cost + (ind - (ind + 1) / 2) * D);
                    }
                }
            }
            if(ind > ind / 2 && ind / 2 > 0) {
                if((ind - ind / 2) >= (A + (ind % 2) * D) / D) {
                    if(nums.count(ind / 2)) {
                        chmin(nums[ind / 2], cost + A + (ind % 2) * D);
                    } else {
                        nums[ind / 2]= cost + A + (ind % 2) * D;
                    }
                } else {
                    if(nums.count(ind / 2)) {
                        chmin(nums[ind / 2], min(cost + A + (ind % 2) * D,
                                                 cost + (ind - ind / 2) * D));
                    } else {
                        nums[ind / 2]= min(cost + A + (ind % 2) * D,
                                           cost + (ind - ind / 2) * D);
                    }
                }
            }
            if(ind > (ind + 2) / 3 && (ind + 2) / 3 > 0) {
                if((ind - (ind + 2) / 3) >= (B + (3 - ind % 3) * D) / D) {
                    if(nums.count((ind + 2) / 3)) {
                        if(ind % 3 == 0) {
                            chmin(nums[(ind + 2) / 3], cost + B);
                        } else {
                            chmin(nums[(ind + 2) / 3],
                                  cost + B + (3 - ind % 3) * D);
                        }
                    } else {
                        if(ind % 3 == 0) {
                            nums[(ind + 2) / 3]= cost + B;
                        } else {
                            nums[(ind + 2) / 3]= cost + B + (3 - ind % 3) * D;
                        }
                    }
                } else {
                    if(nums.count((ind + 2) / 3)) {
                        if(ind % 3 == 0) {
                            chmin(nums[(ind + 2) / 3],
                                  min(cost + B,
                                      cost + (ind - (ind + 2) / 3) * D));
                        } else {
                            chmin(nums[(ind + 2) / 3],
                                  min(cost + B + (3 - ind % 3) * D,
                                      cost + (ind - (ind + 2) / 3) * D));
                        }
                    } else {
                        if(ind % 3 == 0) {
                            nums[(ind + 2) / 3]=
                                min(cost + B, cost + (ind - (ind + 2) / 3) * D);
                        } else {
                            nums[(ind + 2) / 3]=
                                min(cost + B + (3 - ind % 3) * D,
                                    cost + (ind - (ind + 2) / 3) * D);
                        }
                    }
                }
            }
            if(ind > ind / 3 && ind / 3 > 0) {
                if((ind - ind / 3) >= (B + (ind % 3) * D) / D) {
                    if(nums.count(ind / 3)) {
                        chmin(nums[ind / 3], cost + B + (ind % 3) * D);
                    } else {
                        nums[ind / 3]= cost + B + (ind % 3) * D;
                    }
                } else {
                    if(nums.count(ind / 3)) {
                        chmin(nums[ind / 3], min(cost + B + (ind % 3) * D,
                                                 cost + (ind - ind / 3) * D));
                    } else {
                        nums[ind / 3]= min(cost + B + (ind % 3) * D,
                                           cost + (ind - ind / 3) * D);
                    }
                }
            }
            if(ind > (ind + 4) / 5 && (ind + 4) / 5 > 0) {
                if((ind - (ind + 4) / 5) >= (C + (5 - ind % 5) * D) / D) {
                    if(nums.count((ind + 4) / 5)) {
                        if(ind % 5 == 0) {
                            chmin(nums[(ind + 4) / 5], cost + C);
                        } else {
                            chmin(nums[(ind + 4) / 5],
                                  cost + C + (5 - ind % 5) * D);
                        }
                    } else {
                        if(ind % 5 == 0) {
                            nums[(ind + 4) / 5]= cost + C;
                        } else {
                            nums[(ind + 4) / 5]= cost + C + (5 - ind % 5) * D;
                        }
                    }
                } else {
                    if(nums.count((ind + 4) / 5)) {
                        if(ind % 5 == 0) {
                            chmin(nums[(ind + 4) / 5],
                                  min(cost + C,
                                      cost + (ind - (ind + 4) / 5) * D));
                        } else {
                            chmin(nums[(ind + 4) / 5],
                                  min(cost + C + (5 - ind % 5) * D,
                                      cost + (ind - (ind + 4) / 5) * D));
                        }
                    } else {
                        if(ind % 5 == 0) {
                            nums[(ind + 4) / 5]=
                                min(cost + C, cost + (ind - (ind + 4) / 5) * D);
                        } else {
                            nums[(ind + 4) / 5]=
                                min(cost + C + (5 - ind % 5) * D,
                                    cost + (ind - (ind + 4) / 5) * D);
                        }
                    }
                }
            }
            if(ind > ind / 5 && ind / 5 > 0) {
                if((ind - ind / 5) >= (C + (ind % 5) * D) / D) {
                    if(nums.count(ind / 5)) {
                        chmin(nums[ind / 5], cost + C + (ind % 5) * D);
                    } else {
                        nums[ind / 5]= cost + C + (ind % 5) * D;
                    }
                } else {
                    if(nums.count(ind / 5)) {
                        chmin(nums[ind / 5], min(cost + C + (ind % 5) * D,
                                                 cost + (ind - ind / 5) * D));
                    } else {
                        nums[ind / 5]= min(cost + C + (ind % 5) * D,
                                           cost + (ind - ind / 5) * D);
                    }
                }
            }
        }
        cout << nums[1] + D << "\n";
    }
}

Measured memory_bytes: 3696