#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

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

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e2 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

ll dp[maxN][maxN][maxN][2], multi[maxN][maxN][maxN], n, a, b, c, d, ans;

ll cmlt(int as, int bs, int cs) {
	if(!multi[as][bs][cs]) {
		assert(as || bs || cs);
		if(as) multi[as][bs][cs] = cmlt(as - 1, bs, cs) * 2;
		else if(bs) multi[as][bs][cs] = cmlt(as, bs - 1, cs) * 3;
		else multi[as][bs][cs] = cmlt(as, bs, cs - 1) * 5;
	}
	return multi[as][bs][cs];
}

ll solve(int as, int bs, int cs, int tp) {
	auto& mm = dp[as][bs][cs][tp];
	if(mm == -1) {
		mm = LLONG_MAX / 3;
		if(as) {
			ll dg = n / cmlt(as - 1, bs, cs) % 2;
			if(tp == 0) {
				mm = min(mm, dg * d + solve(as - 1, bs, cs, 0));
				mm = min(mm, (dg + 1) * d + solve(as - 1, bs, cs, 1));
			} else {
				mm = min(mm, (2 - dg) * d + solve(as - 1, bs, cs, 0));
				mm = min(mm, (2 - (dg + 1)) * d + solve(as - 1, bs, cs, 1));
			}
		}
		if(bs) {
			ll dg = n / cmlt(as, bs - 1, cs) % 3;
			if(tp == 0) {
				mm = min(mm, dg * d + solve(as, bs - 1, cs, 0));
				mm = min(mm, (dg + 1) * d + solve(as, bs - 1, cs, 1));
			} else {
				mm = min(mm, (3 - dg) * d + solve(as, bs - 1, cs, 0));
				mm = min(mm, (3 - (dg + 1)) * d + solve(as, bs - 1, cs, 1));
			}
		}
		if(cs) {
			ll dg = n / cmlt(as, bs, cs - 1) % 5;
			if(tp == 0) {
				mm = min(mm, dg * d + solve(as, bs, cs - 1, 0));
				mm = min(mm, (dg + 1) * d + solve(as, bs, cs - 1, 1));
			} else {
				mm = min(mm, (5 - dg) * d + solve(as, bs, cs - 1, 0));
				mm = min(mm, (5 - (dg + 1)) * d + solve(as, bs, cs - 1, 1));
			}
		}
	}
	return mm;
}

void inter(int i, int j, int k) {
	{
	ll cr = solve(i, j, k, 0) + i * a + j * b + k * c;
	ll initi = n / cmlt(i, j, k);
	if(initi == 0 || d <= ll(1e12) / initi)
		ans = min(ans, cr + initi * d);
	}
	{
	ll cr = solve(i, j, k, 1) + i * a + j * b + k * c;
	ll initi = n / cmlt(i, j, k) + 1;
	if(d <= ll(1e12) / initi)
		ans = min(ans, cr + initi * d);
	}
}

void pre(int i, int j, int k) {
	inter(i, j, k);
	inter(i + 1, j, k);
	inter(i, j + 1, k);
	inter(i, j, k + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int t;
	cin >> t;
	multi[0][0][0] = 1;
	while(t--) {
		memset(dp, -1, sizeof dp);
		cin >> n >> a >> b >> c >> d;
		dp[0][0][0][0] = 0;
		dp[0][0][0][1] = LLONG_MAX / 3;
		ans = LLONG_MAX / 3;
		int i = 13, j = 6, k = 16;
		for(i = 0; cmlt(i, 0, 0) <= n; i++) {
			for(j = 0; cmlt(i, j, 0) <= n; j++) {
				for(k = 0; cmlt(i, j, k) <= n; k++) {
					pre(i, j, k);
				}
			}
		}
		cout << ans << '\n';
	}
}



Measured memory_bytes: 25104