#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
//using namespace __gnu_pbds;
//typedef tree<
//        pair<long long, int>, // change type
//        null_type,
//        less<pair<long long, int> >, // change type
//        rb_tree_tag,
//        tree_order_statistics_node_update>
//        ordered_set;

//template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;


vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)

typedef long long ll;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
//#define debug(x) cerr << #x << " : " << (x) << " "
const double PI = 3.14159265358979323846;
const double eps = (1e-8);
int isGreater(long double x, long double y)
{
    if (abs(x - y) < eps)
        return 0;
    if (x > y)
        return 1;
    return -1;
}


enum {TWO, THREE, FIVE};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int v[3] = {2, 3, 5};
    ll cost[3], D;
    ll n;
    int tc;
    cin >> tc;
    while(tc--)
    {
        cin >> n >> cost[TWO] >> cost[THREE] >> cost[FIVE] >> D;

        priority_queue<pair<ll, ll> > pq;
        map<ll, ll> dist;
        pq.push({0, n});
        dist[n] = 0;
        while (!pq.empty())
        {
            auto p = pq.top();
            pq.pop();
            ll cur = p.second, c = -p.first;
            if (dist[cur] < c)
                continue;

            if (cur == 1)
            {
                cout << D + c << '\n';
                break;
            }
            for (ll i = max(1LL, cur - 5); i <= cur + 5; ++i)
            {
                for (int j = 0; j < 3; ++j)
                {
                    if (i % v[j] == 0)
                    {
                        ll to = i / v[j];
                        ll d;
                        if (abs(i - to) < cost[j])
                            d = min(cost[j], abs(i - to) * D) + c + 1LL * abs(cur - i) * D;
                        else
                            d = cost[j] + c + 1LL * abs(cur - i) * D;
                        if (!dist.count(to) || dist[to] > d)
                        {
                            dist[to] = d;
                            pq.push({-d, to});
                        }
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 6432