#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a)
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;

inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=500005;
//i_am_noob
int t,n,a,b,c,d,num[70][70][70],arr[70][70][70][2],dp[70][70][70][2],ans;
bool good[70][70][70];

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> a >> b >> c >> d;
        ans=4e18;
        num[0][0][0]=1;
        rep(70) rep1(j,70) rep1(k,70) good[i][j][k]=true;
        rep(70) rep1(j,70) rep1(k,70){
            if(i==0&&j==0&&k==0) continue;
            if(!good[i][j][k]){
                num[i][j][k]=-1;
                if(i!=69) good[i+1][j][k]=false;
                if(j!=69) good[i][j+1][k]=false;
                if(k!=69) good[i][j][k+1]=false;
                continue;
            }
            if(i!=0) num[i][j][k]=2*num[i-1][j][k];
            if(j!=0) num[i][j][k]=3*num[i][j-1][k];
            if(k!=0) num[i][j][k]=5*num[i][j][k-1];
            if(num[i][j][k]>n){
                if(i!=69) good[i+1][j][k]=false;
                if(j!=69) good[i][j+1][k]=false;
                if(k!=69) good[i][j][k+1]=false;
            }
        }
        rep(70) rep1(j,70) rep1(k,70){
            if(num[i][j][k]!=-1){
                arr[i][j][k][0]=n/num[i][j][k];
                arr[i][j][k][1]=ceiling(n,num[i][j][k]);
            }
        }
        dp[0][0][0][0]=dp[0][0][0][1]=0;
        rep(70) rep1(j,70) rep1(k,70){
            if((i==0&&j==0&&k==0)||num[i][j][k]==-1) continue;
            dp[i][j][k][0]=dp[i][j][k][1]=4e18;
            if(i!=0) rep1(ii,2) rep1(jj,2) dp[i][j][k][ii]=min(dp[i][j][k][ii],dp[i-1][j][k][jj]+abs(arr[i][j][k][ii]*2-arr[i-1][j][k][jj]));
            if(j!=0) rep1(ii,2) rep1(jj,2) dp[i][j][k][ii]=min(dp[i][j][k][ii],dp[i][j-1][k][jj]+abs(arr[i][j][k][ii]*3-arr[i][j-1][k][jj]));
            if(k!=0) rep1(ii,2) rep1(jj,2) dp[i][j][k][ii]=min(dp[i][j][k][ii],dp[i][j][k-1][jj]+abs(arr[i][j][k][ii]*5-arr[i][j][k-1][jj]));
        }
        rep(70) rep1(j,70) rep1(k,70) if(num[i][j][k]!=-1) rep1(l,2){
            if((ld)arr[i][j][k][l]*d>3e18) continue;
            //print4(i,j,k,dp[i][j][k][l]);
            ans=min(ans,i*a+j*b+k*c+(arr[i][j][k][l]+dp[i][j][k][l])*d);
        }
        print1(ans);
    }
	return 0;
}


Measured memory_bytes: 9508