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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
  #undef nc
}

typedef long long ll;
typedef long double db;
ll N, A, B, C, D;

typedef pair <ll, ll> pii;

map <ll, ll> dis;
priority_queue <pii, vector <pii>, greater <pii> > Q;

void solve() {
  cin >> N >> A >> B >> C >> D;
  dis.clear();
  while (!Q.empty()) Q.pop();
  Q.push(pii(0, N)), dis[N] = 1;
  while (1) {
    pii p = Q.top();
    ll val = p.first, num = p.second;
    Q.pop();
    if (val > dis[num]) continue;
//    printf("(%lld %lld)\n", val, num);
    if (num == 0) {
      printf("%lld\n", val);
      return;
    }
    ll tmp = num, cnt = 0;
    tmp = num;
    if (num % 2 == 0) {
      tmp = num / 2, cnt = 1;
      if ((!dis[tmp] || dis[tmp] > val + cnt * A)) Q.push(pii(val + cnt * A, tmp)), dis[tmp] = val + cnt * A;
      if ((db) dis[tmp] > (db) tmp * D) {
        if (dis[tmp] > val + tmp * D) Q.push(pii(val + tmp * D, tmp)), dis[tmp] = val + tmp * D;
      }
    }
    tmp = num, cnt = 0;
    if (num % 3 == 0) {
      tmp = num / 3, cnt = 1;
      if ((!dis[tmp] || dis[tmp] > val + cnt * B)) Q.push(pii(val + cnt * B, tmp)), dis[tmp] = val + cnt * B;
      if ((db) dis[tmp] > (db) 2 * tmp * D) {
        if (dis[tmp] > val + 2 * tmp * D) Q.push(pii(val + 2 * tmp * D, tmp)), dis[tmp] = val + 2 * tmp * D;
      }
    }
    tmp = num, cnt = 0;
    if (num % 5 == 0) {
      tmp = num / 5, cnt = 1;
      if ((!dis[tmp] || dis[tmp] > val + cnt * C)) Q.push(pii(val + cnt * C, tmp)), dis[tmp] = val + cnt * C;
      if ((db) dis[tmp] > (db) 4 * tmp * D) {
        if (dis[tmp] > val + 4 * tmp * D) Q.push(pii(val + 4 * tmp * D, tmp)), dis[tmp] = val + 4 * tmp * D;
      }
    }
    tmp = num, cnt = 0;
    while (tmp % 2 != 0) tmp++, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D)) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
    tmp = num, cnt = 0;
    while (tmp % 3 != 0) tmp++, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D)) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
    tmp = num, cnt = 0;
    while (tmp % 5 != 0) tmp++, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D)) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
    tmp = num, cnt = 0;
    while (tmp % 2 != 0 && tmp > 0) tmp--, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D) && tmp >= 0) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
    tmp = num, cnt = 0;
    while (tmp % 3 != 0 && tmp > 0) tmp--, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D) && tmp >= 0) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
    tmp = num, cnt = 0;
    while (tmp % 5 != 0 && tmp > 0) tmp--, cnt++;
    if (cnt && (!dis[tmp] || dis[tmp] > val + cnt * D) && tmp >= 0) Q.push(pii(val + cnt * D, tmp)), dis[tmp] = val + cnt * D;
  }
}

int main() {
  int T = read();
  while (T--) solve();
  return 0;
}

Measured memory_bytes: 7992