#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;
U_MAP mem;

ll f(ll n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return d;
  else if (mem[n] != 0)
    return mem[n];
  else {
    ll hn = n, res = LINF, add = 0;
    while (1) {
      if (hn % 2 == 0) break;
      hn--;
      add += d;
    }
    add += a;
    if (abs(n - hn / 2) <= LINF / d) add = min(add, abs(n - hn / 2) * d);
    res = min(res, f(hn / 2) + add);
    //
    hn = n, add = 0;
    while (1) {
      if (hn % 2 == 0) break;
      hn++;
      add += d;
    }
    add += a;
    if (abs(n - hn / 2) <= LINF / d) add = min(add, abs(n - hn / 2) * d);
    res = min(res, f(hn / 2) + add);
    //
    hn = n, add = 0;
    while (1) {
      if (hn % 3 == 0) break;
      hn--;
      add += d;
    }
    add += b;
    if (abs(n - hn / 3) <= LINF / d) add = min(add, abs(n - hn / 3) * d);
    res = min(res, f(hn / 3) + add);
    //
    hn = n, add = 0;
    while (1) {
      if (hn % 3 == 0) break;
      hn++;
      add += d;
    }
    add += b;
    if (abs(n - hn / 3) <= LINF / d) add = min(add, abs(n - hn / 3) * d);
    res = min(res, f(hn / 3) + add);
    //
    hn = n, add = 0;
    while (1) {
      if (hn % 5 == 0) break;
      hn--;
      add += d;
    }
    add += c;
    if (abs(n - hn / 5) <= LINF / d) add = min(add, abs(n - hn / 5) * d);
    res = min(res, f(hn / 5) + add);
    //
    hn = n, add = 0;
    while (1) {
      if (hn % 5 == 0) break;
      hn++;
      add += d;
    }
    add += c;
    if (abs(n - hn / 5) <= LINF / d) add = min(add, abs(n - hn / 5) * d);
    res = min(res, f(hn / 5) + add);
    mem[n] = res;
    return res;
  }
}

int main(void) {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);

  cin >> q;
  while (q--) {
    ll ushitapunichiakunwara;
    cin >> ushitapunichiakunwara >> a >> b >> c >> d;
    Cout(f(ushitapunichiakunwara));
    mem.clear();
  }
  return 0;
}

Measured memory_bytes: 4136