#include <iostream>
#include <iterator>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
using ll = long long;
int const a[] { 2, 3, 5 };
int b[3], d;
 
ll f(ll n, unordered_map<ll, ll>& memo) {
    ll& ans = memo[n];
    if (n > 0 && ans == 0) {
        ans = 1e12;
        if (n < ans / d)
            ans = n * d;
        for (int i = 3; i--;) {
            int p = a[i], c = b[i];
            ll k = n / p, r = n % p;
            ans = min({ ans, f(k, memo) + r * d + c, r ? f(k + 1, memo) + (p - r) * d + c : ans });
        }
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    for (cin >> t; t--;) {
        ll n;
        cin >> n;
        copy_n(istream_iterator<int>(cin), 3, b);
        cin >> d;
        unordered_map<ll, ll> memo{ {1, d} };
        cout << f(n, memo) << '\n';
    }
    return 0;
}
