#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<62;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

map<ll, ll> mm;

ll f(ll n, ll a, ll b, ll c, ll d) {
	if (n == 0) return 0;
	auto it = mm.find(n);
	if (it != mm.end()) return it->se;
	// cout << n << endl;
	
	ll res = longINF;
	for (int i = 5; i >= -5; --i) {
		ll nex = n + i;
		if (nex < 0) break;
		ll cur = abs(i) * d;
		if (nex == 0) {
			chmin(res, cur);
			continue;
		}
		if (nex % 2 == 0) {
			ll nexv = f(nex / 2, a, b, c, d);
			// if (2. * a / d + 1000 > n) chmin(res, nex / 2 * d + cur + nexv);
			if ((long double)nex / 2 * d + cur + nexv < longINF) chmin(res, nex / 2 * d + cur + nexv);
			if ((long double)a + cur + nexv < longINF) chmin(res, a + cur + nexv);
		}
		if (nex % 3 == 0) {
			ll nexv = f(nex / 3, a, b, c, d);
			// if (3. * b / 2. / d + 1000 > n) chmin(res, nex / 3 * 2 * d + cur + nexv);
			if ((long double)nex / 3 * 2 * d + cur + nexv < longINF) chmin(res, nex / 3 * 2 * d + cur + nexv);
			if ((long double)b + cur + nexv < longINF) chmin(res, b + cur + nexv);
		}
		if (nex % 5 == 0) {
			ll nexv = f(nex / 5, a, b, c, d);
			// if (5. * c / 4. / d + 1000 > n) chmin(res, nex / 5 * 4 * d + cur + nexv);
			if ((long double)nex / 5 * 4 * d + cur + nexv < longINF) chmin(res, nex / 5 * 4 * d + cur + nexv);
			if ((long double)c + cur + nexv < longINF) chmin(res, c + cur + nexv);
		}
	}
	return mm[n] = res;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		mm.clear();
		ll N, A, B, C, D;
		cin >> N >> A >> B >> C >> D;
		
		using pll = pair<ll, ll>;
		priority_queue<pll, vector<pll>, greater<pll>> que;
		que.emplace(0, 0);
		mm[0] = 0;
		while (!que.empty()) {
			ll val = que.top().se;
			ll mon = que.top().fi;
			que.pop();
			if (mm[val] < mon) continue;
			
			if (val + 1 < 1000) {
				ll nv = val + 1;
				ll nm = mon + D;
				auto it = mm.find(nv);
				if (it == mm.end() || it->se > nm) {
					mm[nv] = nm;
					que.emplace(nm, nv);
				}
			}
			if (val - 1 >= 0) {
				ll nv = val - 1;
				ll nm = mon + D;
				auto it = mm.find(nv);
				if (it == mm.end() || it->se > nm) {
					mm[nv] = nm;
					que.emplace(nm, nv);
				}
			}
			if (val * 2 < 1000) {
				ll nv = val * 2;
				ll nm = mon + A;
				auto it = mm.find(nv);
				if (it == mm.end() || it->se > nm) {
					mm[nv] = nm;
					que.emplace(nm, nv);
				}
			}
			if (val * 3 < 1000) {
				ll nv = val * 3;
				ll nm = mon + B;
				auto it = mm.find(nv);
				if (it == mm.end() || it->se > nm) {
					mm[nv] = nm;
					que.emplace(nm, nv);
				}
			}
			if (val * 5 < 1000) {
				ll nv = val * 5;
				ll nm = mon + C;
				auto it = mm.find(nv);
				if (it == mm.end() || it->se > nm) {
					mm[nv] = nm;
					que.emplace(nm, nv);
				}
			}
		}
		
		cout << f(N, A, B, C, D) << endl;

	}
	return 0;
}


Measured memory_bytes: 7084