#include<bits/stdc++.h>
using namespace std;

map<long long ,long long > M;
long long st[3]={2,3,5};
long long fy[4];

long long dfs(long long n){
    if(M.count(n))return M[n];
    if(n==0)return M[0]=0;
    M[n]=1LL<<60;
    if(M[n]/fy[3]/n)M[n]=min(M[n],n*fy[3]);
    for(int i=0;i<3;i++){
        if(n%st[i]==0)M[n]=min(M[n],dfs(n/st[i])+fy[i]);
        else{
            M[n]=min(M[n],dfs(n/st[i])+fy[i]+n%st[i]*fy[3]);
            M[n]=min(M[n],dfs(n/st[i]+1)+fy[i]+(st[i]-n%st[i])*fy[3]);
        }
    }
    return M[n];
}

int main(){
    int T;
    cin>>T;
    while(T--){
        M.clear();
        long long N;
        scanf("%lld%lld%lld%lld%lld",&N,&fy[0],&fy[1],&fy[2],&fy[3]);
        printf("%lld\n",dfs(N));
    }
}