#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
// Abbreviations
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
#define pq priority_queue
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define ff(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define FF(i, a, b) for (int i = (int)(b); i >= (int)(a); --i)
#define trav(a, x) for (auto &a: x)
#define sz(a) (int)((a).size())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define upper_bound upb
#define lower_bound lwb
 
using namespace std;
using namespace __gnu_pbds;
 
// Constants
const int ooi = 2e9;
const long long ool = 4e18;
const int mod = 1e9 + 7; // 998244353
const double PI = acos(-1);
const long double eps = 1e-9;
 
// Abbreviations
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef queue<int> qi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
typedef long double lld;
typedef unsigned long long ui64;
 
// Min - max
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

// Fast IO
template<typename T> inline void read(T &x) {
	char c;
	bool neg = false;
	while ((!isdigit(c = getchar())) && c != '-');
	if (c == '-') {
		c = getchar(); neg = true;
	}
	x = c - 48;
	while (isdigit(c = getchar())) {
		x = x * 10 + (c - 48);
	}
	if (neg) x = -x;
}
template<typename T> inline void Write(T x) {
	if (x > 9) Write(x / 10);
	putchar(x % 10 + 48);
}
template<typename T> inline void write(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	Write(x);
}

// Debug

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
	return '"' + s + '"';
}

string to_string(const char* s) {
	return to_string((string) s);
}

string to_string(bool b) {
	return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(v[i]);
	}
	res += "}";
	return res;
}

template <size_t N>
string to_string(bitset<N> v) {
	string res = "";
	for (size_t i = 0; i < N; i++) {
		res += static_cast<char>('0' + v[i]);
	}
	return res;
}

template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

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
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// Tree-order statistics
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

// Commonly used functions
inline i64 gcd(i64 a, i64 b) { // Use __gcd(a, b) instead for int
	i64 r;
	while (b) {
		r = a % b; a = b; b = r;
	}
	return a;
}

inline i64 lcm(i64 a, i64 b) {
	return (a / gcd(a, b) * b);
}

inline i64 fpow(i64 a, i64 b, i64 m = mod) {
	i64 r = 1;
	for (; b > 0; b >>= 1) {
		if (b & 1) r = r * a % m;
		a = a * a % m;
	}
	return r;
}

inline void addmod(int &a, int val, int m = mod) {
	if ((a = a + val) >= m) a -= m;
}

inline void submod(int &a, int val, int m = mod) {
	if ((a = a + val) < 0) a += m;
}

inline int mult(int a, int b, int m = mod) {
	return (i64) a * b % m;
}

inline int inv(int a, int m = mod) {
	return fpow(a, m - 2, m);
}

inline bool isPrime(i64 x) {
	if (x <= 3) return (x >= 2);
	if (x % 2 == 0 || x % 3 == 0) return false;
	for (i64 i = 5; i * i <= x; i += 6) {
		if (x % i == 0 || x % (i + 2) == 0) return false;
	}
	return true;
}

#ifdef LOCAL_DEFINE
  mt19937 rnd(42); // Seed 42, output 1608637542
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
inline int mrand() {
	return abs((int) rnd());
}

// Main program starts here

void solve() {
	i64 a, b, c, d, n;
	cin >> n >> a >> b >> c >> d;
	vector<pair<int, i64> > ops;
	ops.eb(2, a); ops.eb(3, b); ops.eb(5, c);

	map<i64, i64> mp;
	mp[0] = 0;
	mp[1] = d;

	function<i64(i64)> dfs = [&](i64 x) {
		if (mp.find(x) != mp.end()) return mp[x];
		i64 res = ool;
		if ((lld) d * (lld) x < res) res = d * x;
		trav(p, ops) {
			int num = p.fi;
			i64 cost = p.se;
			res = min(res, dfs(x / num) + cost + d * (x % num));
			if (x % num != 0) {
				res = min(res, dfs(x / num + 1) + cost + d * (num - x % num));
			}
		}
		return mp[x] = res;
	};

	cout << dfs(n) << '\n';
}

int main(void) {	
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout.precision(10); cout << fixed;
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif

	int t;
	cin >> t;
	while (t--) solve();

#ifdef LOCAL_DEFINE
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 4412