//                 ....
//             ....      ..
//          ...           .
//        ..        .......
//     ...          .......
//   ...          .. .......
//  ..          ..     .......
// ..          ..        ......
// ..         ..          .......
// ..        ..            .... ..
//  ..     ..                .......
//                            ... ...
//                              ......
//                               .......
//                                 ......
//                                  ......
//                                   .......
//                                     ......
//                                      .......
//                                       .......
//                                         ......                 ......
//                                          .......           ........ ..
//                                            ......      ........ ........
//                                             ....... ............ ........
//                                              .............................
//                                              ...................... ........
//                                           ...................................
//                                       ................................ .......
//                                    ............................................
//                                   ............................................
//                                 ............................................
//                                 ..........................................
//                                  ......................................
//                                   ..................................
//                                     .............................
//                                      .........................
//                                        .........................
//                                   ................................
//                                   ..............................
//                                      ....................



#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
using namespace std;

//g++-9 -Wl,-stack_size -Wl,100000000 test.cpp -o test
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#define INFF 9223372036854775807
#define INF 1000000000000000001

#define debug1 cout<<"helo 1"<<endl;
#define debug2 cout<<"helo 2"<<endl;
#define endl "\n"
#define couti(a) printf("%d ",a)
#define coutl(a) printf("%lld ",a)
#define nline printf("\n")
#define cini(a) scanf("%d",&a)
#define cinl(a) scanf("%lld",&a)

#define mp make_pair
#define f first
#define pb push_back
#define pob pop_back
#define s second
#define t third

#define int long long
#define ll long long
#define LL long long

#define PI 3.14159265358979323846264338327950288419716939937510582097

#define priorqmax priority_queue<LL>
#define priorqmin priority_queue<LL,vector<LL>,greater<LL> >
#define len length()
#define vi vector<int>
#define vl vector<ll>
#define ve vector
#define lsti list<int>
#define pairi pair<int,int>
#define pairl pair<ll,ll>
#define mset(a) memset(a,0,sizeof(a))
#define FOR(j,a,n) for(int j=a;j<n;++j)
#define FOR1(j,a,n) for(int j=a;j>=n;--j)


class comp_ordered_set_pair{
public:
   bool operator() (const pairi &a,const pairi &b) const{
      if(a.f==b.f)
         return a.s<b.s;
      return a.f<b.f;
   }
};
typedef tree<
   pairi,
   null_type,
   comp_ordered_set_pair,
   rb_tree_tag,
   tree_order_statistics_node_update>
   ordered_set_pair;

class trio{public: int first,second, third;};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ifstream iFile("input.txt");
// ofstream oFile("output.txt");

//#define MOD 1000000007
//#define MOD 987654319
#define MOD 998244353


ll gcdExtended(ll a, ll b, ll *x, ll *y){
   if (a == 0){
      *x = 0, *y = 1;
      return b;
   }
   ll x1, y1;
   ll gcd = gcdExtended(b%a, a, &x1, &y1);
   *x = y1 - (b/a) * x1;
   *y = x1;
   return gcd;
}
ll modInverse(ll a, ll m){
   ll x, y;
   ll g = gcdExtended(a, m, &x, &y);
   ll res = (x%m + m) % m;
   return res;
}

LL power(LL x,LL y){
   //(x^y)%MOD
   LL ans=1,s=x;
   while(y){
      if(y&1){
         ans*=s;
         ans%=MOD;
      }
      s*=s;
      s%=MOD;
      y>>=1;
   }
   return ans;
}

// .................................................. START
// Check if int needs to be converted to long long  _/\_

int a,b,c,d;
ve<__int128> hell;
map<int,__int128>dp;
__int128 func(int n){
   
   if(n<5)
      return hell[n];
   if(dp.find(n)!=dp.end())
      return dp[n];
   
   __int128 ans=(__int128)d*n;
   for(int i=-4;i<=4;++i){
      int  temp = i+n;
      if(temp>0){
         if(temp%2==0)
            ans=min(ans,d*abs(i)+func(temp/2)+a);
         if(temp%3==0)
            ans=min(ans,d*abs(i)+func(temp/3)+b);
         if(temp%5==0)
            ans=min(ans,d*abs(i)+func(temp/5)+c);
      }
   }
   dp[n]=ans;
   return ans;
}

int32_t main(){
//   fastio;
   int t;
   cin>>t;
   hell.assign(6,0);
   while(t--) {
      int n;
      cin >> n >> a >> b >> c >> d;
      dp.clear();
      hell[1]=d;
      hell[2]=min({2*d,d+a});
      hell[3]=min({3*d,d+b,2*(d+a),d*2+a});
      hell[4]=min(2*d,d+a)+min(2*d,a);
      hell[4]=min({(int)hell[3]+d,(int)hell[4],d+c+d,(int)hell[2]+b+2*d});
      
      
      __int128 ans = func(n);
      cout<<(int)ans<<endl;
   }
   

   return 0;
}


Measured memory_bytes: 7072