#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int T;
  cin >> T;
  for(int _=0;_<T;_++){
    ll N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;

    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    map<ll,ll> mp;
    mp[N]=0;
    pq.push(m_p(0,N));
    while(!pq.empty()){
      ll cost=pq.top().fi;
      ll now=pq.top().se;
      pq.pop();

      ll next_cost;
      ll next_now;
      ll tmp;
      bool flag;
      if(now%5==0){
        next_cost=cost+C;
        next_now=now/5;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }
      else{
        tmp=5-now%5;
        next_cost=cost+C+D*tmp;
        next_now=(now+tmp)/5;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
        tmp=now%5;
        next_cost=cost+C+D*tmp;
        next_now=(now-tmp)/5;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }

      if(now%3==0){
        next_cost=cost+B;
        next_now=now/3;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }
      else{
        tmp=3-now%3;
        next_cost=cost+B+D*tmp;
        next_now=(now+tmp)/3;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
        tmp=now%3;
        next_cost=cost+B+D*tmp;
        next_now=(now-tmp)/3;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }

      if(now%2==0){
        next_cost=cost+A;
        next_now=now/2;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }
      else{
        tmp=2-now%2;
        next_cost=cost+A+D*tmp;
        next_now=(now+tmp)/2;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
        tmp=now%2;
        next_cost=cost+A+D*tmp;
        next_now=(now-tmp)/2;
        flag=false;
        if(!mp.count(next_now)) flag=true;
        else if(mp.at(next_now)>next_cost)  flag=true;
        if(flag){
          mp[next_now]=next_cost;
          pq.push(m_p(next_cost,next_now));
        }
      }

      tmp=1e16/D;
      if(now>tmp) continue;
      next_cost=cost+D*now;
      next_now=0;
      flag=false;
      if(!mp.count(next_now)) flag=true;
      else if(mp.at(next_now)>next_cost)  flag=true;
      if(flag){
        mp[next_now]=next_cost;
      }
    }

    //for(const auto& [key,value]:mp) cout << key << " -> " << value << endl;
    cout << mp[0] << endl;
  }

  return 0;
}

Measured memory_bytes: 4372