#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % MOD;
      x = x * x % MOD;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

__int128_t func(){
  __int128_t n = in();
  __int128_t a = in();
  __int128_t b = in();
  __int128_t c = in();
  __int128_t d = in();
  map<__int128_t,__int128_t> m;
  m[n] = 0;

  auto func =
    [&](__int128_t x,__int128_t y){
      if(m.count(x)){
        chmin(m[x],y);
      }else{
        m[x] = y;
      }
    };

  while(m.size()){
    pair<__int128_t,__int128_t> current = *m.rbegin();
    m.erase(current.first);
    __int128_t x = current.first;
    __int128_t y = current.second;
    if(x==0)return y;
    func(0,y+d*x);
    if(x&1){
      func(x/2,y+a+d);
      if(x/2+1!=x){
        func(x/2+1,y+a+d);
      }
    }else{
      func(x/2,y+a);
    }
    if(x%3==0){
      func(x/3,y+b);
    }else{
      func(x/3,y+b+d*(x%3));
      if(x/3+1!=x){
        func(x/3+1,y+b+d*(3-x%3));
      }
    }
    if(x%5==0){
      func(x/5,y+c);
    }else{
      func(x/5,y+c+d*(x%5));
      if(x/5+1!=x){
        func(x/5+1,y+c+d*(5-x%5));
      }
    }
  }
  return INF;
}
int print_uint128(__int128_t n) {
  if (n == 0)  return printf("0\n");

  char str[40] = {0}; // log10(1 << 128) + '\0'
  char *s = str + sizeof(str) - 1; // start at the end
  while (n != 0) {
    if (s == str) return -1; // never happens

    *--s = "0123456789"[n % 10]; // save last digit
    n /= 10;                     // drop it
  }
  return printf("%s\n", s);
}
int main(){
  int t = in();
  rep(i,t){
    __int128_t ans = func();
    print_uint128(ans);

  }
  return 0;
}


Measured memory_bytes: 3864