#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <numeric>
#include <climits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <utility>
////////////////////////////////////////////////
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
////////////////////////////////////////////////
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
const ll MOD = 1000000007;  // 1e9+7
////////////////////////////////////////////////
vecll w, x, y, z;
map<ll, ll> mp;
ll dfs(int id, ll n) {
  ll a = w[id];
  ll b = x[id];
  ll c = y[id];
  ll d = z[id];

  if (mp.count(n) > 0) {
    // cout << n << " " << mp[n] << endl;
    return mp[n];
  }
  // cout << n << endl;
  ll res = 1e18;
  ll tmp = 0;
  ///////////////2
  ll l = n / 2LL;
  ll r = 0;
  if (n > 1e10) {
    tmp = abs(n - 2LL * l) * d + a;
  } else {
    tmp = min(abs(n - l) * d, (n - 2LL * l) * d + a);
  }
  res = min(res, tmp + dfs(id, l));
  if (n % 2LL != 0) {
    r = l + 1LL;
    if (n > 1e10) {
      tmp = abs(n - 2LL * r) * d + a;
    } else {
      tmp = min((n - r) * d, abs(n - 2LL * r) * d + a);
    }
    res = min(res, tmp + dfs(id, r));
  }
  ///////////////3
  if (n >= 3LL) {
    l = n / 3LL;
    if (n > 1e10) {
      tmp = abs(n - 3LL * l) * d + b;
    } else {
      tmp = min((n - l) * d, (n - 3LL * l) * d + b);
    }
    res = min(res, tmp + dfs(id, l));
    if (n % 3LL != 0) {
      r = l + 1LL;
      if (n > 1e10) {
        tmp = abs(n - 3LL * r) * d + b;
      } else {
        tmp = min((n - r) * d, abs(n - 3LL * r) * d + b);
      }
      res = min(res, tmp + dfs(id, r));
    }
  }
  ///////////////5
  if (n >= 5LL) {
    l = n / 5LL;
    if (n > 1e10) {
      tmp = abs(n - 5LL * l) * d + c;
    } else {
      tmp = min((n - l) * d, (n - 5LL * l) * d + c);
    }
    res = min(res, tmp + dfs(id, l));
    if (n % 5LL != 0) {
      r = l + 1LL;
      if (n > 1e10) {
        tmp = abs(n - 5LL * r) * d + c;
      } else {
        tmp = min((n - r) * d, abs(n - 5LL * r) * d + c);
      }

      res = min(res, tmp + dfs(id, r));
    }
  }
  mp[n] = res;
  // cout << n << " " << res << endl;
  return mp[n] = res;
}
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  int t;
  cin >> t;
  vecll n(t, 0);
  w.resize(t);
  x.resize(t);
  y.resize(t);
  z.resize(t);
  REP(i, t) { cin >> n[i] >> w[i] >> x[i] >> y[i] >> z[i]; }
  REP(i, t) {
    mp.clear();
    mp[0LL] = 0;
    mp[1LL] = z[i];
    // cout << n[i] << endl;
    cout << dfs(i, n[i]) << endl;
  }
}
//////////////////////////////////////////////


Measured memory_bytes: 4476