#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<Z A,Z...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

ll a,b,c,d,ans;
set<ll> s;

void solve(ll n,ll sum) {
  if(sum>MAXL||s.count(n)) return;
  if(n<MAX) ans=min(ans,sum+n*d);
  if(n<=1) return;
  ll x=n%2;
  if(!x) solve(n/2,sum+a);
  else {
    solve(n-x,sum+x*d);
    solve(n+(2-x),sum+(2-x)*d);
  }
  ll y=n%3;
  if(!y) solve(n/3,sum+b);
  else {
    solve(n-y,sum+y*d);
    solve(n+(3-y),sum+(3-y)*d);
  }
  ll z=n%5;
  if(!z) solve(n/5,sum+c);
  else {
    solve(n-z,sum+z*d);
    solve(n+(5-z),sum+(5-z)*d);
  }
}

void Main() {
  ll T;
  R T;
  while(T--) {
    ll n;
    cin >> n >> a >> b >> c >> d;
    ans=LONG_MAX-1;
    //solve(n,0);
    map<ll,ll> m;
    m[n]=0;
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(0,n));
    while(!que.empty()) {
      P p=que.top();que.pop();
      n=p.S;
      ll sum=p.F;
      if(m[n]<sum) continue;
      {
        ll w=n*d;
        if(w>=n&&w/d==n) ans=min(ans,sum+w);
      }
      ll x=n%2;
      if(!x) {
        ll e=n/2,cc=sum+a;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      } else {
        ll e=n-x,cc=sum+x*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
        e=n+(2-x),cc=sum+(2-x)*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      }
      x=n%3;
      if(!x) {
        ll e=n/3,cc=sum+b;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      } else {
        ll e=n-x,cc=sum+x*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
        e=n+(3-x),cc=sum+(3-x)*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      }
      x=n%5;
      if(!x) {
        ll e=n/5,cc=sum+c;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      } else {
        ll e=n-x,cc=sum+x*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
        e=n+(5-x),cc=sum+(5-x)*d;
        if(!m.count(e)||m[e]>cc) {
          m[e]=cc;
          que.push(P(cc,e));
        }
      }
    }
    pr(ans);
    /*
    ll x=1,ans=MAXL;
    REP(l,1,60) {
      ll x=l;
      rep(i,61) {
        ll y=x;
        rep(j,61) {
          ll z=y;
          rep(k,61) {
            if(abs(z-n)<MAX) ans=min(ans,i*a+j*b+k*c+abs(z-n)*d+d);
            if(z>n) break;
            z*=5;
          }
          if(y>n) break;
          y*=3;
        }
        if(x>n) break;
        x*=2;
      }
    }
    pr(ans);
    */
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 13460