#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

#include <ext/pb_ds/assoc_container.hpp>
struct my_hash {
    template<typename ...> using to_void = void;
    template<typename T, typename = void> struct is_container : false_type {};
    template<typename T> struct is_container<T, to_void<decltype(declval<T>().begin()), decltype(declval<T>().end())>> : true_type {};
    static const uint64_t FIXED_RANDOM;
    static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const { return splitmix64(x + FIXED_RANDOM); }
    template<typename T, typename U> size_t operator()(const pair<T, U>& x) const {
      size_t ret = operator()(x.first); return ((ret << 6) ^ (ret >> 15)) + operator()(x.second); }
    template<typename T, typename = typename enable_if<is_container<T>::value>::type > size_t operator()(const T& x) const {
      size_t ret = FIXED_RANDOM; for (auto c : x) { ret = ((ret << 6) ^ (ret >> 15)) + operator()(c); } return ret; }
    template<size_t i = 0, typename... Ts> size_t operator()(const tuple<Ts...>& x, size_t ret = FIXED_RANDOM) const {
      if constexpr(i < sizeof...(Ts)) return operator()<i + 1>(x, ((ret << 6) ^ (ret >> 15)) + operator()(get<i>(x))); else return ret; }
};
const uint64_t my_hash::FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count() ^ (uint64_t) (make_unique<char>().get());
template<typename K, typename V> using hashmap = __gnu_pbds::gp_hash_table<K, V, my_hash>;
template<typename V> using hashset = __gnu_pbds::gp_hash_table<V, __gnu_pbds::null_type, my_hash>;

namespace utils{
constexpr bool use_stdio = false;
ostream* out = &cout;
FILE* stdio_out = stdout;
const bool __ = [](){ if constexpr(!use_stdio){ ios_base::sync_with_stdio(false); cin.tie(nullptr);
  cout << fixed; cout << setprecision(12); cerr << fixed; cerr << setprecision(12); } return true; }();
template<typename ...> using to_void = void;
template<typename T, typename = void> struct is_container : false_type {};
template<typename T> struct is_container<T, to_void<decltype(declval<T>().begin()), decltype(declval<T>().end())>> : true_type {};

inline void rd(int& x) { if constexpr(use_stdio) scanf("%d", &x); else cin >> x; }
inline void rd(long long& x) { if constexpr(use_stdio) scanf("%lld", &x); else cin >> x; }
inline void rd(double& x) { if constexpr(use_stdio) scanf("%lf", &x); else cin >> x; }
inline void rd(long double& x) { if constexpr(use_stdio){ double y; scanf("%lf", &y); x=y; } else cin >> x; }
inline void rd(char& x) { if constexpr(use_stdio) scanf(" %c", &x); else cin >> x; }
inline void rd(char* x) { if constexpr(use_stdio) scanf("%s", x); else cin >> x; }
inline void rd(string& x) { if constexpr(use_stdio) assert(false); else cin >> x; }
template<typename T, typename enable_if<!use_stdio && is_integral<T>::value>::type* = nullptr> inline void rd(T& x) { cin >> x; }
template<typename T> inline void rd(T* x);
template<typename T, typename enable_if<is_container<T>::value>::type* = nullptr> inline void rd(T& x);
template<typename... Ts> inline void rd(tuple<Ts...>& x);
template<typename T, typename U> inline void rd(pair<T, U>& x) { rd(x.first); rd(x.second); }
template<typename T, typename enable_if<is_container<T>::value>::type* = nullptr> inline void rd(T& x) { for(auto& v : x) rd(v); }
template<typename T, typename U, typename... Ts> inline void rd(T&& t, U&& u, Ts&&... ts) {
  rd(forward<T>(t)); rd(forward<U>(u), forward<Ts>(ts)...); }
template<typename... Ts> inline void rd(tuple<Ts...>& x) { static_assert(sizeof...(Ts) > 0);
  constexpr auto apply_rd = [](auto&&... xs) { rd(xs...); }; apply(apply_rd, x); }
template<typename T> inline void rd(T* x) { rd(*x); }

inline void prt(const int& x) { if constexpr(use_stdio) fprintf(stdio_out, "%d", x); else *out << x; }
inline void prt(const long long& x) { if constexpr(use_stdio) fprintf(stdio_out, "%lld", x); else *out << x; }
inline void prt(const double& x) { if constexpr(use_stdio) fprintf(stdio_out, "%.12f", x); else *out << x; }
inline void prt(const long double& x) { if constexpr(use_stdio) fprintf(stdio_out, "%.12f", (double)x); else *out << x; }
inline void prt(const char& x) { if constexpr(use_stdio) fprintf(stdio_out, "%c", x); else *out << x; }
inline void prt(const char* x) { if constexpr(use_stdio) fprintf(stdio_out, "%s", x); else *out << x; }
inline void prt(const string &x) { if constexpr(use_stdio) fprintf(stdio_out, "%s", x.c_str()); else *out << x; }
template<typename T, typename enable_if<!use_stdio && is_integral<T>::value>::type* = nullptr> inline void prt(const T& x) { *out << x; }
template<typename T, typename enable_if<is_container<T>::value>::type* = nullptr> inline void prt(const T& x);
template<typename... Ts> inline void prt(const tuple<Ts...>& x);
template<typename T, typename U> inline void prt(const pair<T, U>& x) { prt(x.first); prt(' '); prt(x.second); }
template<typename T, typename enable_if<is_container<T>::value>::type* = nullptr> inline void prt(const T& x) {
  if (x.begin() != x.end()) { prt(*x.begin()); for(auto it = x.begin(); ++it != x.end(); ) { prt(' '); prt(*it); } } }
template<typename T, typename U, typename... Ts> inline void prt(T&& t, U&& u, Ts&&... ts) {
  prt(forward<T>(t)); prt(' '); prt(forward<U>(u), forward<Ts>(ts)...); }
template<typename... Ts> inline void prt(const tuple<Ts...>& x ) { static_assert(sizeof...(Ts) > 0);
  constexpr auto apply_prt = [](auto&&... xs) { prt(xs...); }; apply(apply_prt, x); }
inline void wt() { prt('\n'); }
template<typename... Ts> inline void wt(Ts&&... ts) { prt(forward<Ts>(ts)...); wt(); }

#ifdef MY_DEBUG_FLAG
inline void enter_db() { if constexpr(use_stdio) stdio_out = stderr; else out = &cerr; }
inline void leave_db() { if constexpr(use_stdio) stdio_out = stdout; else out = &cout; }
inline void db() { enter_db(); prt('\n'); leave_db(); }
template<typename... Ts> inline void db(Ts&&... ts) { enter_db(); prt(forward<Ts>(ts)...); wt(); leave_db(); }
#define db(...) utils::db("Debug(", #__VA_ARGS__, ") == (", __VA_ARGS__, ")")
#else
#define db(...)
#endif // define(MY_DEBUG_FLAG)
constexpr int slen(char*s){ return (int) strlen(s); }
template<typename T, typename U, typename enable_if<is_container<T>::value>::type* = nullptr> inline T& resize(T& x, U n) { 
  x.resize(n); return x; }
void flush() { if constexpr(use_stdio) fflush(stdout); else cout << std::flush; }
} using utils::rd, utils::prt, utils::wt, utils::slen, utils::resize, utils::flush;

#define pb emplace_back
#define x first
#define y second
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define dec(i,n,a) for(int i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()

constexpr int inf = 0x3f3f3f3f;
constexpr ld EPS = 1e-9;
constexpr int MAXN = 1e5 + 10;
constexpr int LOGN = 20;
constexpr int mod = 1000000007;

ll a, b, c, d;
hashmap<ll, ll> dp;

ll solve(ll n) {
  if (n == 0) return 0;
  if (n == 1) return d;
  if (n == 2) return min(2*d, d+a);
  if (dp.find(n) != dp.end() && dp[n] != -1) return dp[n];
  ll ans = 1e16;
  if ((ld) d * n < 1e17) ans = min(ans, d * n);
  for (auto [k, v] : vector<pii>{{a, 2}, {b, 3}, {c, 5}}) {
    if (n < v) continue;
    ll r = n % v;
    ans = min(ans, solve(n / v) + k + r * d);
    ans = min(ans, solve(n / v + 1) + k + (v - r) * d);
  }
  return dp[n] = ans;
}

void solve(){
  for(auto [k, v] : dp) dp[k] = -1;
  ll n;
  rd(n, a, b, c, d);
  ll ans = solve(n);
  wt(ans);
}

int main() {
  int t;
  rd(t);
  while(t--) solve();
}


Measured memory_bytes: 5612