#define MST(a, b) memset(a,b,sizeof(a))
#define ALL(v) (v).begin(),(v).end()
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL,LL> pll;
#include <ext/pb_ds/priority_queue.hpp>
#define rep(i,a,b) for(int i = (a) ; i <= (b) ; ++i)
#define per(i,a,b) for(int i = (a) ; i >= (b) ; --i)
#define fors(i,S) for(int i = (S) ; i ; i = (i-1)&(S))
#define forn(i,n) for(int i = 0 ; i < (n) ; ++i)

using namespace __gnu_pbds;
//typedef __gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> heap;
//typedef heap::point_iterator iter;
typedef unsigned long long ULL;
//typedef __int128 LL128;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

int system_const;
namespace fast_IO{
    const int maxbuff = 1<<17;
    char ibuff[maxbuff],obuff[maxbuff];
    inline char Getchar(){
        static char *p1=ibuff,*p2=ibuff;
        if(p1 == p2) {
            p1 = ibuff;
            p2 = ibuff+fread(ibuff,1,maxbuff,stdin);
            if(p1 == p2) return -1;
        }
        return *p1++;
    }

    int optr = 0;
    inline void Putchar(char c) {
        if(optr == maxbuff) {fwrite(obuff,1,optr,stdout);optr = 0;}
        obuff[optr++] = c;
    }

    inline void Flush() {
        fwrite(obuff,1,optr,stdout);
    }

    template<class T>
    void read_number(T &x) {
        x = 0;
        char c;int f = 0;
        for(c = Getchar() ; c != '-' && (c < '0' || c > '9') ; c = Getchar());
        if(c == '-') f = 1;
        else x = c-'0';
        for(c = Getchar() ; c >= '0' && c <= '9' ; c = Getchar()) x = x*10+c-'0';
        if(f) x = -x;
    }

    void read_string(string &s) {
        s.clear();
        char c;
        for(c = Getchar() ; c == ' ' || c == '\n' ; c = Getchar());
        s.push_back(c);
        for(c = Getchar() ; c != ' ' && c != '\n' ; c = Getchar())
            s.push_back(c);
    }

    template<class T>
    void write_number(T &x) {
        static int dec[20];int len = 0;
        if(x == 0) {Putchar('0');return ;}
        if(x < 0) {Putchar('-');x = -x;}
        while(x) {
            dec[++len] = x%10;
            x /= 10;
        }
        while(len) Putchar(dec[len--]+'0');
    }

    void write_string(const string &s) {
        for(int i = 0 ;i < s.size() ; ++i)
            Putchar(s[i]);
    }
}
void read(string &s) {
    if(system_const == 0) {
        using namespace fast_IO;
        read_string(s);
    }
    else cin >> s;
}
template<class T> void read(T &x) {
    if(system_const == 0) {
        using namespace fast_IO;
        read_number(x);
    }
    else cin >> x;
}
void write(const string &s) {
    if(system_const == 0) {
        fast_IO::write_string(s);
    }
    else cout << s;
}
template<class T> void write(T &x) {
    if(system_const == 0) {
        fast_IO::write_number(x);
    }
    else cout << x;
}
void writeln(const string &s) {
    write(s);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar('\n');
    }
    else cout << endl;
}
template<class T> void writeln(T x) {
    write(x);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar('\n');
    }
    else cout << '\n';
}
void writesp(const string &s) {
    write(s);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar(' ');
    }
    else cout << ' ';
}

template<class T> void writesp(T x) {
    write(x);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar(' ');
    }
    else cout << ' ';
}
void set_program_type(int t = 0) {
    system_const = t;
    if(t) {
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
    }
}
void finish_program(int t = 0) {
    if(!t) fast_IO::Flush();
}

void init_all(int t = 0,string s = "output") {
#ifdef LOCAL
    if ((t >> 1) & 1) freopen("input", "r", stdin);
    if ((t >> 2) & 1) freopen(s.c_str(), "w", stdout);
#endif
}

template <int MOD=998244353, class T = int> struct Modular {
    T value;
    static const T MOD_value = MOD;

    Modular(T v = 0) { value = v % MOD; if (value < 0) value += MOD;}
    Modular(T a, T b) : value(0){ *this += a; *this /= b;}

    Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
    Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
    Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

    friend Modular mexp(Modular a, long long e) {
        Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
        return res;
    }
    friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

    Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
    friend Modular operator+(Modular a, Modular const &b) { return a += b; }
    friend Modular operator-(Modular a, Modular const &b) { return a -= b; }
    friend Modular operator-(Modular const &a) { return 0 - a; }
    friend Modular operator*(Modular a, Modular const &b) { return a *= b; }
    friend Modular operator/(Modular a, Modular const &b) { return a /= b; }
    friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
    friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
    friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}

};



int pre_ask_time;
void show_time() {
    int now = clock();
    cout << now-pre_ask_time << endl;
    pre_ask_time = now;
}

template<class T> void cmin(T &x,const T&y) {if(x > y) x = y;}
template<class T> void cmax(T &x,const T&y) {if(x < y) x = y;}

struct Vector{
    LL x,y;
    Vector(LL x = 0,LL y = 0):x(x),y(y){}
    friend LL operator *(const Vector &A,const Vector &B) {return A.x*B.x+A.y*B.y;}
    friend Vector operator - (const Vector &A,const Vector &B) {return Vector(B.x-A.x,B.y-A.y);}
    friend LL operator /(const Vector &A,const Vector &B) {return A.x*B.y-A.y*B.x;}
};

unordered_map<LL,LL> mp;
LL n,a,b,c,d;

LL f(LL x) {
    if(mp.count(x)) return mp[x];
    LL res = 1e18;
    if(res/d > x) res = x*d;
    {
        LL t = 2,k = x/t,v = a;
        if(k != x) cmin(res,(x-k*t)*d+v+f(k));
        if(k+1 != x) cmin(res,((k+1)*t-x)*d+v+f(k+1));
    }
    {
        LL t = 3,k = x/t,v = b;
        if(k != x) cmin(res,(x-k*t)*d+v+f(k));
        if(k+1 != x) cmin(res,((k+1)*t-x)*d+v+f(k+1));
    }
    {
        LL t = 5,k = x/t,v = c;
        if(k != x) cmin(res,(x-k*t)*d+v+f(k));
        if(k+1 != x) cmin(res,((k+1)*t-x)*d+v+f(k+1));
    }
    return mp[x] = res;
}

void solve() {
    cin >> n >> a >> b >> c >> d;
    mp.clear();
    mp[0] = 0;
    mp[1] = d;
    cout << f(n) << endl;
}

signed main() {
    //srand((int)time(0));
    pre_ask_time = clock();
    init_all(3);

    //init();
    set_program_type(0);
    int T = 1;
    //read(T);
    cin >> T;
    //scanf("%d",&T);
    rep(i,1,T) {
        //printf("Case #%lld: ",i);
        solve();
    }

    finish_program(0);

    return 0;
}


Measured memory_bytes: 4256