#include <iostream>
#ifdef MBP
#include "stdc++.h"
#else
#include <bits/stdc++.h>
#endif

#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define REP(i, n) for (long long int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (long long int i = 1, i##_len = (n); i <= i##_len; ++i)
#define REP_R(i, n) for (long long int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((long long int)(x).size())
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

//#define DEBUG

#ifdef DEBUG
#define OUT(x) std::cout << (x) << std::endl
#define OUT2(x, y) std::cout << (x) << "," << (y) << std::endl
#define OUT3(x, y, z) std::cout << (x) << "," << (y) << "," << (z) << std::endl
#define OUTSP(x) std::cout << (x) << " ";
#define OUTLF std::cout << std::endl
#define OUTPA(p) OUT2(p.first, p.second)
#else
#define OUT(x) NULL
#define OUT2(x, y) NULL
#define OUT3(x, y, z) NULL
#define OUTPA(p) NULL
#define OUTSP(p) NULL
#define OUTLF NULL
#endif

#define INF INT_MAX
#define INFLL LLONG_MAX
#define PB push_back
#define MOD 1000000007LL

#define LSB(x) __builtin_ctzll(x)
#define MSB(x) 64LL - __builtin_clzll(x) - 1LL
#define MSBINT(x) 32LL - __builtin_clz(x)
#define BITCNT(x) __builtin_popcountll(x)

using namespace std;
using uif = uint_fast64_t;
//using ll = long long int;
using ll = mp::cpp_int;
using vec = vector<ll>;
using mat = vector<vector<ll>>;
using pa = pair<ll, ll>;
using tTree = __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template <class T>
inline void input(T &arr)
{
  ll n = arr.size();
  REP(i, n)
  cin >> arr[i];
}
template <class T>
inline void input2(T &arr1, T &arr2)
{
  ll n = arr1.size();
  REP(i, n)
  cin >> arr1[i] >> arr2[i];
}
template <class T>
inline void inputPA(T &arr)
{
  ll n = arr.size();
  REP(i, n)
  cin >> arr[i].first >> arr[i].second;
}
template <class T>
inline void outArr(T &arr)
{
  for (auto x : arr)
  {
    OUTSP(x);
  }
  OUTLF;
}

template <class T>
using PQ = priority_queue<T>;
template <class T>
using PQG = priority_queue<T, vector<T>, greater<T>>;

const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
const ll dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

template <class T>
bool chmax(T &, const T &);
template <class T>
bool chmin(T &, const T &);

ll qp(ll a, ll b);
ll qp(ll a, ll b, ll mo);

ll mod_pow(ll, ll);
ll mod_add(ll, ll);
ll mod_mul(ll, ll);
ll mod_div(ll, ll);
void make_fact(ll);
void make_invfact(ll);
void init_fact();

ll combination(ll, ll);

#define FACSIZE 200002LL

//ll invfac[FACSIZE];
//ll fac[FACSIZE];

ll n, a, b, c, d;
vec I{2, 3, 5};
vec K(3);
unordered_map<long long int, ll> um;

ll f(ll x)
{
  long long int k = x.convert_to<long long int>();
  OUT(x);
  if (x == 0)
    return 0;
  else if (x == 1)
    return d;
  else if (x == 2)
    return min(2LL * d, a + d);
  else if (x == 3)
    return min(3LL * d, b + d);

  if (um.find(k) != end(um))
    return um[k];

  ll res = INFLL;

  REP(i, 3)
  {

    ll prev = x / I[i] * I[i];
    ll nex = (x / I[i] + (ll)(1LL)) * I[i];

    res = min(res, min((x - prev) * d + K[i], (x - prev / I[i]) * d) + f(prev / I[i]));

    if (nex / I[i] != x)
      res = min(res, min((nex - x) * d + K[i], (x - nex / I[i]) * d) + f(nex / I[i]));
  }

  return um[k] = res;
}

int main(void)
{
  long long int t;
  cin >> t;
  REP(i, t)
  {

    cin >> n >> a >> b >> c >> d;
    K[0] = a;
    K[1] = b;
    K[2] = c;
    um.clear();
    cout << f(n) << endl;
  }
  return 0;
}

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


Measured memory_bytes: 5204