#include <bits/stdc++.h>

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

map<ll, ll> memo;

ll solve(ll n, ll a, ll b, ll c, ll d) {
  if(n == 0) return 0;
  if(n == 1) return d;
  if(memo.find(n) != memo.end()) {
    return memo[n];
  }

  ll res = LLONG_MAX;

  if(n % 2) {
    ll cost = a;
    if((n+1) / 2 < LLONG_MAX / d) chmin(cost, d * ((n+1)/2));
    chmin(res, solve((n+1)/2, a, b, c, d) + cost + d);
    cost = a;
    if((n-1)/2 < LLONG_MAX / d) chmin(cost, d * ((n-1)/2));
    chmin(res, solve((n-1)/2, a, b, c, d) + cost + d);
  } else {
    ll cost = a;
    if(n/2 < LLONG_MAX / d) chmin(cost, d * (n/2));
    res = solve(n/2, a, b, c, d) + cost;
  }

  if(n % 3) {
    ll tmpn = n;
    ll now = 0;
    while (tmpn % 3) {
      now += d;
      tmpn++;
    }
    ll cost = b;
    if((tmpn / 3) * 2 < LLONG_MAX / d) chmin(cost, d * (tmpn/3) * 2);
    chmin(res, solve(tmpn/3, a, b, c, d) + cost + now);
    tmpn = n;
    now = 0;
    while(tmpn % 3) {
      now += d;
      tmpn--;
    }
    cost = b;
    if((tmpn / 3) * 2 < LLONG_MAX / d) chmin(cost, d * (tmpn/3) * 2);
    chmin(res, solve(tmpn/3, a, b, c, d) + cost + now);
  } else {
    ll cost = b;
    if((n/3) * 2 < LLONG_MAX / d) chmin(cost, d * (n/3) * 2);
    chmin(res, solve(n/3, a, b, c, d) + b);
  }

  if(n % 5) {
    ll tmpn = n;
    ll now = 0;
    while (tmpn % 5) {
      now += d;
      tmpn++;
    }
    ll cost = c;
    if(tmpn / 5 * 4 < LLONG_MAX / d) chmin(cost, d * (tmpn / 5 * 4));
    chmin(res, solve(tmpn/5, a, b, c, d) + cost + now);
    tmpn = n;
    now = 0;
    while(tmpn % 5) {
      now += d;
      tmpn--;
    }
    cost = c;
    if(tmpn / 5 * 4 < LLONG_MAX / d) chmin(cost, d * (tmpn / 5 * 4));
    chmin(res, solve(tmpn/5, a, b, c, d) + c + now);
  } else {
    ll cost = c;
    if(n / 5 * 4 < LLONG_MAX / d) chmin(cost, d * (n / 5 * 4));
    chmin(res, solve(n/5, a, b, c, d) + c);
  }

  return memo[n] = res;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int t; cin >> t;
  while(t--) {
    ll n, a, b, c, d; cin >> n >> a >> b >> c >> d;
    memo.clear();
    cout << solve(n, a, b, c, d) << endl;
  }

}
























Measured memory_bytes: 4436