#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define Rep(i,n) for(int i=1;i<=(n);++i)
using LL = long long;
using ULL = unsigned long long;

const LL INF = 1e18;

LL y[3]{2, 3, 5}, z[4];
map<LL, LL> dp;

LL f(LL n) {
    if(n == 0) return 0;
    if(n == 1) return z[3];
    auto it = dp.find(n);
    if(it != dp.end()) return it->second;
    LL x = INF;
    rep(i, 3) {
        LL d = n % y[i];
        x = min(x, f(n/y[i]) + d * z[3] + z[i]);
        x = min(x, f((n+y[i]-1)/y[i]) + (y[i] - d) * z[3] + z[i]);
    }
    if(x / z[3] >= n) x = min(x, n * z[3]);
    return dp[n] = x;
}

int main()
{
    int T;
    cin >> T;
    while(T--) {
        LL n;
        cin >> n;
        rep(i, 4) cin >> z[i];
        dp.clear();
        cout << f(n) << endl;
    }
	return 0;
}
