#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const ll mx=1e18;
map<ll,ll>mp;
ll a,b,c,d;
ll solve(ll n){
    if(n==1) return d;
    if(n==0) return 0;
    ll l1,l2,l3,r1,r2,r3;
    if(mp.count(n)) return mp[n];
    l1=n/2;
    r1=(n+1)/2;
    l2=n/3;
    r2=(n+2)/3;
    l3=n/5;
    r3=(n+4)/5;
    ll res=1e18;
    if(n<=mx/d) res=n*d;
    res=min(res,solve(l1)+(n-l1*2)*d+a);
    res=min(res,solve(r1)+(r1*2-n)*d+a);
    res=min(res,solve(l2)+(n-l2*3)*d+b);
    res=min(res,solve(r2)+(r2*3-n)*d+b);
    res=min(res,solve(l3)+(n-l3*5)*d+c);
    res=min(res,solve(r3)+(r3*5-n)*d+c);
    return mp[n]=res;
}
int main(){
    int t;
    cin>>t;
    while(t--){
       ll n;
       mp.clear();
       cin>>n>>a>>b>>c>>d;
       cout<<solve(n)<<'\n';
    }
}