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

map<long long, long long> dp;
long long N, A, B, C, D;

vector<long long> v = {2,3,5}, c;

long long solve(long long N) {
    if (dp.count(N))    return dp[N];

    long long ans = 1e18;
    if (N <= ans/D)     ans = min(ans, N*D);

    for (int i=0; i<3; i++) {
        long long p = v[i];
        long long C = c[i];
        long long r = N%p;
        ans = min(ans, r*D+solve(N/p)+C);
        if (r > 0)  ans = min(ans, (p-r)*D+solve(N/p+1)+C);
    }

    return dp[N] = ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin>>t;

    while (t--) {
        cin>>N>>A>>B>>C>>D;

        c = {A, B, C};

        dp.clear();
        dp[0] = 0;
        dp[1] = D;

        cout<<solve(N)<<endl;
    }
}
