//                          **********  YATIN KWATRA  ********** 

//AC bakshi Rabha

#include <bits/stdc++.h>
#define ll                      long long 
#define ull                     unsigned long long 
#define FIO                     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                      vector<int>
#define vll                     vector<ll>
#define pq                      priority_queue
#define uom                      unordered_map                
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int> 
#define pll                     pair<long,long>
#define mll                     map<ll,ll>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define vvll                    vector<vll>
#define mod                     1000000007
#define pi                      3.1415926535897932384626433832795
// #define node                    Node

using namespace std;

void INPUT() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

}

ll ans = LLONG_MAX;

ll n,a,b,c,d;
uom<ll,ll>dp;

ll f(ll s, uom<ll,ll>&dp)
  {
    if(s==0LL) return 0LL;
    if(s==1LL) return d;  

    if(dp.count(s)) return dp[s];

    // so we can reach 0 or 1 ,

    // Case- we can reach 1 or 0 , we can reach 1 from 2*i,3*i,4*i
    // so we start in the reverse direction, we can reach 1 or 0
    // from floor(s/2) or ceil(s/2) and similarly for 3 and 5

    ll op1 = (s/2LL)*(2LL) ; // gives req s to reach floor of s/2
    // the position it gives has to be reached by inc or dec of 1

    ll op2 = ((s+1LL)/2LL)*(2LL);

    // for ceil we do add 1 because if s was divisible by 2
    // floor and ceil would be same
    // if it is 11 floor is 5 reachable from 10 
    // to reach ceil value , we jump from (n+1)/2
    // beacuse by adding 1 a non divisible no
    // becomes divisible by 2

    // similarly we add 2 for 3 and 4 for 5

    ll op3 = (s/3LL)*(3LL);
    ll op4 = ((s+2LL)/3LL)*(3LL);
    ll op5 = (s/5LL)*(5LL);
    ll op6 = ((s+4LL)/5LL)*(5LL);

    ll ans = 1e18;

  // if i travel with eac
  //  if(s < ans/d) ans = s*d;

    if(s<(ans/d)) ans = s*d;
    ans = min(ans,llabs(op1-s)*d + a + f(op1/2LL,dp));
    ans = min(ans,llabs(op2-s)*d + a + f(op2/2LL,dp));
    ans = min(ans,llabs(op3-s)*d + b + f(op3/3LL,dp));
    ans = min(ans,llabs(op4-s)*d + b + f(op4/3LL,dp));
    ans = min(ans,llabs(op5-s)*d + c + f(op5/5LL,dp));
    ans = min(ans,llabs(op6-s)*d + c + f(op6/5LL,dp));

    dp[s] = ans;
    return ans;

  }


void solve()
{ 
   
    cin >> n  >> a >> b >> c >> d;


    dp.clear();
   
    ll cost = f(n,dp);
    cout << cost << endl;
       
}
int main() {
    
    FIO
    INPUT();
    
    int t;
    t = 1;
    cin >> t;
    
    while(t--)
    {
       solve();
    }
    return 0;
}


Measured memory_bytes: 4008