#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

// =========ここまでテンプレ============

struct hoge
{
    ll cost;
    ll number;
    friend bool operator<(const hoge &x, const hoge &y)
    {
        return tie(x.cost, x.number) > tie(y.cost, y.number);
        // return tie(x.number, x.cost) < tie(y.number, y.cost);
    }
    friend bool operator==(const hoge &x, const hoge &y)
    {
        return x.cost == y.cost && x.number == y.number;
    }
};

int main()
{
    int t;
    cin >> t;
    vector<array<ll, 5>> cases;
    rep(i, t)
    {
        ll n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        cases.push_back(array<ll, 5>{n, a, b, c, d});
    }
    rep(i, t)
    {
        ll n, a, b, c, d;
        n = get<0>(cases[i]);
        a = get<1>(cases[i]);
        b = get<2>(cases[i]);
        c = get<3>(cases[i]);
        d = get<4>(cases[i]);

        priority_queue<hoge> que;
        que.push(hoge{0, n});
        map<ll, bool> alreadies;
        while (true)
        {
            hoge x = que.top();
            que.pop();
            if (alreadies[x.number] == false)
            {
                alreadies[x.number] = true;
                if (x.number == 0)
                {
                    cout << x.cost << endl;
                    break;
                }
                else
                {
                    if (x.cost + x.number * d > 0)
                        que.push(hoge{x.cost + x.number * d, 0});
                    int r2 = x.number % 2;
                    if (r2 == 0)
                    {
                        if (x.cost + a > 0)
                            que.push(hoge{x.cost + a, x.number / 2});
                    }
                    else
                    {
                        if (x.cost + d + a > 0)
                            que.push(hoge{x.cost + d + a, (x.number + 1) / 2});
                        if (x.number > 1 && x.cost + d + a > 0)
                            que.push(hoge{x.cost + d + a, (x.number - 1) / 2});
                    }
                    int r3 = x.number % 3;
                    if (r3 == 0)
                    {
                        if (x.cost + b > 0)
                            que.push(hoge{x.cost + b, x.number / 3});
                    }
                    else
                    {
                        if (x.cost + b + (3 - r3) > 0)
                            que.push(hoge{x.cost + b + (3 - r3) * d, (x.number + (3 - r3)) / 3});
                        if (x.number > 2 && x.cost + b + r3 * d > 0)
                            que.push(hoge{x.cost + b + r3 * d, (x.number - r3) / 3});
                    }
                    int r5 = x.number % 5;
                    if (r5 == 0)
                    {
                        if (x.cost + c > 0)
                            que.push(hoge{x.cost + c, x.number / 5});
                    }
                    else
                    {
                        if (x.cost + c + (5 - r5) * d > 0)
                            que.push(hoge{x.cost + c + (5 - r5) * d, (x.number + (5 - r5)) / 5});
                        if (x.number > 5 && x.cost + c + r5 * d > 0)
                            que.push(hoge{x.cost + c + r5 * d, (x.number - r5) / 5});
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 3960