/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class APayToWin {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int t; cin >> t;
      while(t--) {
        ll n, a, b, c, d; cin >> n >> a >> b >> c >> d;
        unordered_map<ll, ll> mp;

        priority_queue<P, vector<P>, greater<>> que;
        que.emplace(0, n);
        mp[n] = 0;
        mp[0] = LLONG_MAX/2;
        while(!que.empty()) {
          auto pa = que.top(); que.pop();
          auto cost = pa.first;
          auto u = pa.second;
          debug(cost, u);
          if (cost > mp[u]) continue;

          auto k = u%5;
          // down
          auto v = u/5;
          auto cc = cost + c + k*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + (u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }

          v++;
          cc = cost + c + (5-k)*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + abs(u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }

          k = u%3;
          v = u/3;
          cc = cost + b + k*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + abs(u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }

          v++;
          cc = cost + b + (3-k)*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + abs(u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }

          k = u%2;
          v = u/2;
          cc = cost + a + k*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + (u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }

          v++;
          cc = cost + a + (2-k)*d;
          if (abs(u-v) < 1e+9) chmin(cc, cost + abs(u-v)*d);
          if (mp.find(v) == mp.end() || mp[v] > cc) {
            mp[v] = cc;
            debug(cc, v);
            if (cc < mp[0]) que.emplace(cc, v);
          }
        }

        cout << mp[0] << endl;

      }
    }
};

signed main() {
  APayToWin solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 4364