#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define F first
#define S second
#define all( x ) x.begin() , x.end()
#define pb push_back
#define mp make_pair
#define uniq( x ) sort( all( x ) ) , x.resize( unique( all( x ) ) - x.begin())
 
const int maxn = 2e5 + 10 ;
const int INF = 1e18 ;
 
int n , a , b , c , d , t , dp[ maxn ] ;
vector< int > vv ;
 
void solve()
{
 cin >> n >> a >> b >> c >> d ;
 
 for(int i = 1 ; i <= n ; i *= 2){
   for(int j = i ; j <= n ; j *= 3){
      for(int k = j ; k <= n ; k *= 5){
         vv.pb( n/k ) ;
         vv.pb( (n+k-1)/k ) ;
      }
   }
 }
 
 
 uniq( vv );
 
// cout << vv.size() << "\n" ;
 
 dp[ 0 ] = d ;
 for(int i = 1 ; i < vv.size() ; i ++){
   int x = vv[ i ];
 
   dp[ i ] = 9*INF ;
 
   long double xx = x , dd = d , check = 9e18 ;
   long double val = xx*dd ;
   if( val < check ){
     dp[ i ] = x*d ;
   }
 
   int x1 = x/2 , y1 = (x+1)/2 , dx1 = x%2 , dy1 = (2-(x%2))%2 ;
   int x2 = x/3 , y2 = (x+2)/3 , dx2 = x%3 , dy2 = (3-(x%3))%3;
   int x3 = x/5 , y3 = (x+4)/5 , dx3 = x%5 , dy3 = (5-(x%5))%5;
 
   int indx1 = lower_bound( all( vv ) , x1 ) - vv.begin() ;
   int indx2 = lower_bound( all( vv ) , x2 ) - vv.begin() ;
   int indx3 = lower_bound( all( vv ) , x3 ) - vv.begin() ;
   int indy1 = lower_bound( all( vv ) , y1 ) - vv.begin() ;
   int indy2 = lower_bound( all( vv ) , y2 ) - vv.begin() ;
   int indy3 = lower_bound( all( vv ) , y3 ) - vv.begin() ;
 
 //  if( indx1 == vv.size() || indx2 == vv.size() || indx3 == vv.size()|| indy1 == vv.size()|| indy2 == vv.size()|| indy3 == vv.size())
 //     cout << "NOOOOOOOo\n" ;
 
   dp[ i ] = min( dp[ i ] , dp[ indx1 ] + dx1*d + a ) ;
   dp[ i ] = min( dp[ i ] , dp[ indx2 ] + dx2*d + b ) ;
   dp[ i ] = min( dp[ i ] , dp[ indx3 ] + dx3*d + c ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy1 ] + dy1*d + a ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy2 ] + dy2*d + b ) ;
   dp[ i ] = min( dp[ i ] , dp[ indy3 ] + dy3*d + c ) ;
 
 }
 
// cout << vv[ vv.size()-1 ] << "\n" ;
 
 cout << dp[ vv.size()-1 ] << "\n" ;
}
 
signed main()
{
 ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
 
 cin >> t ;
 
 while( t -- ){
  solve();
 }
 
    return 0;
}