#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
map< ll, ll > dp;
ll n, a, b, c, d;
ll fast_exp(ll base, ll exp)
{
  ll res=1;
  while(exp>0)
    {
      if(exp%2==1) res=(res*base);
      base=(base*base);
      exp/=2;
    }
  return res;
}
ll compute( ll A)
{
    if(dp.find(A) == dp.end()) dp[A] = -1;
    if(dp[A]!= -1) return dp[A];
    ll ans = 1e18;
    ll cur ;
    // do 2
    if( A >= 2)
    {
        cur = llabs((A/2)*2 - A)*d + a + compute(A/2);
        ans = MIN2(ans, cur);
        if(A%2)
        {
            cur = llabs((A/2 + 1)*2 - A)*d + a + compute(A/2 + 1);
            ans = MIN2(ans, cur);
        }
    }
    if( A >= 3)
    {
        // do 3
        cur = llabs((A/3)*3 - A)*d + b + compute(A/3);
        ans = MIN2(ans, cur);
        if(A%3)
        {
            cur = llabs((A/3 + 1)*3 - A)*d + b + compute(A/3 + 1);
            ans = MIN2(ans, cur);
        }
    }
    // do 5
    if( A >= 5)
    {
        cur = llabs((A/5)*5 - A)*d + c+ compute(A/5);
        ans = MIN2(ans, cur);

        if(A%5)
        {
            cur = llabs((A/5 + 1)*5 - A)*d + c+ compute(A/5 + 1);
            ans = MIN2(ans, cur);
        }
    }
    // run down to 0 with just operation 'D'
    if(log2(A) + log2(d) < 61 )
            ans = MIN2(ans, A*d);
    return dp[A] = ans;
}
int main()
{
    she_told_me_dont_worry
    int t;
    cin>>t;
    while(t--)
    {
        dp.clear();
        ll i, j, k;
        cin>>n>>a>>b>>c>>d;
        ll b2 = log2(n) + 1, b3 = (double)(log(n)/log(3)) + 1, b5 = (double)(log(n)/log(5)) + 1;
        dp[0] = 0;
        FOR0(i, b2)
        {
            FOR0(j, b3)
            {
                FOR0(k, b5)
                {
                    if( (double)(i + (double)j*log2(3) + (double)k*log2(5)) + 2 > log2(n)) continue;
                    ll cur = fast_exp(2, i);
                    cur *= fast_exp(3, j);
                    cur *= fast_exp(5, k);
                    dp[n/cur] = -1;
                    if(n%cur) dp[n/cur + 1] = -1;
                }
            }
        }
        cout<<compute(n)<<endl;
    }
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 4828