#include <bits/stdc++.h>

const long long l018 = 1000000000000000000;

using namespace std;

int n;
vector<vector<vector<long long> > > abc;

void init(){
    long long a,b,c;
    for(a = 0;a < 61;a++){
        abc.push_back(vector<vector<long long> >());
        for(b = 0;b < 60;b++){
            abc[a].push_back(vector<long long>());
            for(c = 0;c < 59;c++){
                long long v;
                if(c == 0){
                    if(b == 0){
                        if(a == 0){
                            v = 1;
                        }
                        else{
                            v = abc[a-1][0][0] * 2;
                        }
                    }
                    else{
                        v = abc[a][b-1][0] * 3;
                    }
                }
                else{
                    v = abc[a][b][c-1] * 5;
                }
                abc[a][b].push_back(v);
                if(v > l018) break;
            }
            if(c == 0) break;
        }
    }
}


void solve(){
    long long n;
    int i,j,k;
    cin >> n;
    long long a,b,c,d;
    cin >> a >> b >> c >> d;
    vector<vector<vector<pair<long long,long long> > > > dp;
    long long ans = l018;
    for(i = 0;i < abc.size();i++){
        dp.push_back(vector<vector<pair<long long,long long> > >());
        for(j = 0;j < abc[i].size();j++){
            dp[i].push_back(vector<pair<long long,long long> >());
            for(k = 0;k < abc[i][j].size();k++){
                long long p = n,o = n;
                if(n % abc[i][j][k] == 0){
                    p = n / abc[i][j][k];
                    o = n / abc[i][j][k];
                }
                else{
                    if(k){
                        p = min(p,dp[i][j][k-1].first-4*(n/abc[i][j][k]));
                        p = min(p,dp[i][j][k-1].second-4*(n/abc[i][j][k]));
                        o = min(o,dp[i][j][k-1].first-4*(n/abc[i][j][k])+6-2*(n%abc[i][j][k]/abc[i][j][k-1]));
                        if(n % abc[i][j][k-1]){
                            o = min(o,dp[i][j][k-1].second-4*(n/abc[i][j][k])+4-2*(n%abc[i][j][k]/abc[i][j][k-1]));
                        }
                    }
                    if(j){
                        p = min(p,dp[i][j-1][k].first-2*(n/abc[i][j][k]));
                        p = min(p,dp[i][j-1][k].second-2*(n/abc[i][j][k]));
                        o = min(o,dp[i][j-1][k].first-2*(n/abc[i][j][k])+4-2*(n%abc[i][j][k]/abc[i][j-1][k]));
                        if(n % abc[i][j-1][k]){
                            o = min(o,dp[i][j-1][k].second-2*(n/abc[i][j][k])+2-2*(n%abc[i][j][k]/abc[i][j-1][k]));
                        }
                    }
                    if(i){
                        p = min(p,dp[i-1][j][k].first-n/abc[i][j][k]);
                        p = min(p,dp[i-1][j][k].second-n/abc[i][j][k]);
                        o = min(o,dp[i-1][j][k].first-n/abc[i][j][k]+3-2*(n%abc[i][j][k]/abc[i-1][j][k]));
                        if(n % abc[i-1][j][k]){
                            o = min(o,dp[i-1][j][k].second-n/abc[i][j][k]+1-2*(n%abc[i][j][k]/abc[i-1][j][k]));
                        }
                    }
                }
                dp[i][j].push_back(make_pair(p,o));
                long long da = min(p,o);
                if((double)da*(double)d < 999999999999999999.9){
                    da = a*i+b*j+c*k+da*d;
                    if(ans > da) ans = da;
                }
            }
        }
    }
    cout << ans << endl;
}

int main(){
    init();
    int t;
    cin >> t;
    for(int i = 0;i < t;i++) solve();
}


Measured memory_bytes: 4136