#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif


template <typename Tu>
static inline constexpr bool is_multiplication_safe(Tu a, Tu b)
{
    return !a || b <= std::numeric_limits<Tu>::max() / a;
}

ll d[3];
map<ll, ll> m;
ll N, A, B, C, D;
ll ans;

ll dfs(ll val){
	if(m.find(val) != m.end()){
		return m[val];
	}
	if(val == 1) return 0;
	ll res = LLINF;
	if(is_multiplication_safe(D, (val-1))) res = D * (val - 1);
	rep(i, 3){
		ll res2 = 0;
		ll tmp = val - val % d[i];
		res2 += (val % d[i]) * D;
		if(tmp == 0){
			res = min(res, res2 - D);
			continue;
		}
		res2 += dfs(tmp / d[i]);
		if(i == 0) res2 += A;
		else if(i == 1) res2 += B;
		else if(i == 2) res2 += C;
		res = min(res, res2);
	}
	return m[val] = res;
}
int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	int T; cin >> T;
	d[0] = 2; d[1] = 3; d[2] = 5;
	rep(i, T){
		m.clear();
		cin >> N >> A>> B >> C >> D;
		ans = LLINF;
		rep(i, 6){
			ans = min(ans, dfs(N + i) + i * D);
		}
		cout << ans + D << endl;
	}
	return 0;
}
