#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define b_e(a) a.begin(),a.end() //sort(b_e(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define p_b push_back
#define SZ(x) ((ll)(x).size()) //size()がunsignedなのでエラー避けに
#define endk '\n'


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //

// #include <atcoder/all>
// using namespace atcoder;

// ゼロ除算エラーの対策をしていないので注意
// 関数の引数の評価順序が未規定のため、ceil_divide(ii(), ii())はNG
ll ceil_divide(ll a, ll b) {
  return (a + b - 1) / b;
}

ll a, b, c, d;
map<ll, ll> resmap;

// Nから減らしていって0にすると考える
ll calc_recursive(ll n){
  if (n == 0) return 0;
  if (n == 1) return d; // 増やして2, 3, 5にしてから割っても1に戻ってしまうので、この場合は -1 するしかない
  if ( resmap.find(n) != resmap.end() ) return resmap[n];

  ll res = LINF;

  // +-1 だけをして辿り着く場合
  // ※最大で N*D = 10^18*10^9 に達してしまうが、+-4してから1/5したり、+-2してから1/3したりを繰り返せば、明らかに答えはLINF以下で収まるので、N*Dが大きすぎる場合は無視していい
  // よって、n*dがオーバーフローしない場合だけ chmin する
  if (n < (LINF / d)) chmin(res, n * d);

  // (2の倍数でなければ+-してから) 1/2 ※
  ll mod2 = n % 2;
  if (mod2==0) chmin(res, a + calc_recursive(n/2));
  else{
    chmin(res, d + a + calc_recursive((n+1)/2)); // + してから 1/2
    chmin(res, d + a + calc_recursive((n-1)/2));
  }

  // 1/3
  ll mod3 = n % 3;
  if (mod3==0) chmin(res, b + calc_recursive(n/3));
  else{
    chmin(res, d * (3 - mod3) + b + calc_recursive(ceil_divide(n, 3)));
    chmin(res, d * mod3 + b + calc_recursive(n/3));    
  }

  // 1/5
  ll mod5 = n % 5;
  if (mod5==0) chmin(res, c + calc_recursive(n/5));
  else{
    chmin(res, d * (5 - mod5) + c + calc_recursive(ceil_divide(n, 5)));
    chmin(res, d * mod5 + c + calc_recursive(n/5));    
  }

  if ( resmap.find(n) != resmap.end() ) chmin(resmap[n], res);
  else resmap[n] = res;

  return resmap[n];

}

// --------- library end - //



int main(){

  ll t = il();

  rep(i, t){
    ll n;

    // mapの初期化
    resmap.clear();

    cin >> n >> a >> b >> c >> d;

    cout << calc_recursive(n) << endk;
  }


  

}



Measured memory_bytes: 4536