#include <iostream>
#include <map>
using namespace std;
using ll = unsigned long long;
#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)

ll A[3], D;
map<ll, ll> dp;
ll dfs(ll N) {
  ll ans = D*N;
  ll ps[] = {2, 3, 5};
  if (N == 0) return 0;
  if (N == 1) return D;
  if (dp.count(N) > 0) return dp[N];
  rep(i, 3) {
    ll p = ps[i];
    ans = min(ans,
        min(dfs(N/p)+A[i]+D*(N%p),
          dfs((N+p-1)/p)+A[i]+D*((N+p-1)/p*p-N)));
  }
  return dp[N] = ans;
}

int main() {
  int t; cin >> t;

  rep(i, t) {
    ll N; cin >> N;
    rep(j, 3) cin >> A[j];
    cin >> D;

    map<ll, ll> dp2;
    swap(dp, dp2);
    cout << dfs(N) << endl;
  }

  return 0;
}
