#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

map<ll, ll> cost;
const ll INF = 1e18;
ll a[6], d;
ll get(ll n) {
  if (cost.find(n) != cost.end()) return cost[n];
  ll val = INF;
  for (int k: {2, 3, 5}) {
    for (ll nn: {n / k, (n + k - 1) / k}) {
      val = min(val, a[k] + get(nn) + llabs(n - nn*k) * d);
    }
  }
  if (val / d >= n) val = n * d;
  return cost[n] = val;
}

int main() {
#ifdef LOCAL_EXEC
	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  int t; cin >> t;
  while (t--) {
    ll n; cin >> n >> a[2] >> a[3] >> a[5] >> d;
    cost.clear();
    cost[0] = 0;
    cost[1] = d;
    cout << get(n) << endl;
  }

  return 0;
}
