#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
using u64 = uint_fast64_t;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr u64 MOD = 1'000'000'007LL;
constexpr f80 PI = 3.14159265358979323846;
#define ASSERT(expr...) assert((expr))
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(int i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(int i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef pair<i64,i64> P;
typedef v(i64) vi;
typedef v(vi) vvi;
typedef v(vvi) vvvi;
typedef v(P) vp;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;

  map<i64, i64> mp;
  mp[N] = 0;
  mp[0] = INF;
  set<i64> que;
  que.insert(N);
  i64 pos, cost;
  while(!que.empty()){
    vector<i64> nxt;
    for(auto &p:que){
      if(p!=0) nxt.emplace_back(p);
    }
    que.clear();
    for(auto &p:nxt){
      if(p<INF/D) chmin(mp[0],mp[p]+D*p);

      if(p%2==0){
        pos = p/2;
        cost = mp[p] + A;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      } else {
        pos = (p+1)/2;
        cost = mp[p] + D + A;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }

        pos = (p-1)/2;
        cost = mp[p] + D + A;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      }

      if(p%3==0){
        pos = p/3;
        cost = mp[p] + B;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      } else {
        pos = (p+(3-p%3))/3;
        cost = mp[p] + D * (3-p%3) + B;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }

        i64 pos = (p-p%3)/3;
        i64 cost = mp[p] + D * (p%3) + B;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      }

      if(p%5==0){
        pos = p/5;
        cost = mp[p] + C;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      } else {
        pos = (p+(5-p%5))/5;
        cost = mp[p] + D * (5-p%5) + C;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }

        i64 pos = (p-p%5)/5;
        i64 cost = mp[p] + D * (p%5) + C;
        if(mp[pos]==0) mp[pos] = INF;
        if(mp[pos]>cost){
          mp[pos] = cost;
          que.insert(pos);
        }
      }
    }
  }
  cout << mp[0] << "\n";
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);

  i64 T;
  cin >> T;
  rep(_, T){
    Main();
  }
}

Measured memory_bytes: 4560