#include <bits/stdc++.h>

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;  // 2次元配列
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
//    cout << fixed << setprecision(15);

    i32 t, n, a,b,c,d; cin >> t;
    i32 divider[] = {2,3,5};
    vi costs(3);
    map<i32, i64> mp;
    queue<i32> st;
    rep(_, t) {
        cin >> n >> costs[0] >> costs[1] >> costs[2] >> d;
        i32 MAX = infll;
        if(log10(d) + log10(n) < 18) MAX = d * n;
        mp[0] = MAX;
        mp[n] = 0;
        st.push(n);
        while(st.size()) {
            i32 num = st.front(), lb, ub; st.pop();
            if(num == 1) {
                chmin(mp[0], mp[num]+d);
                continue;
            }
            rep(i,3) {
                i32 div = divider[i];
                lb = num/div * div;
                ub = (num+div-1)/div * div;

                if(mp.find(lb/div) == mp.end()) mp[lb/div] = infll;
                if(mp.find(ub/div) == mp.end()) mp[ub/div] = infll;
                i64 cost1 = min<i64>(d * abs(num-lb) + costs[i], (MAX!=infll ? d * abs(num-lb/div) : infll));
                i64 cost2 = min<i64>(d * abs(num-ub) + costs[i], (MAX!=infll ? d * abs(num-ub/div) : infll));
                bool do1 = chmin(mp[lb/div], mp[num] + cost1);
                bool do2 = chmin(mp[ub/div], mp[num] + cost2);

                if(do1) {
//                    debug(lb/div);
                    st.push(lb/div);
                }
                if(do2) {
//                    debug(ub/div);
                    st.push(ub/div);
                }
            }
        }
        cout << mp[0] << '\n';
        mp.clear();
    }

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 4728