#include <cmath>
#include <queue>
#include <random>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 61;
mt19937 mt(2005251804);
int rand_rng(int l, int r) {
	uniform_int_distribution<int> p(l, r - 1);
	return p(mt);
}
long long solve(long long N, long long A, long long B, long long C, long long D) {
	vector<long long> pw2 = { 1 }, pw3 = { 1 }, pw5 = { 1 };
	while (pw2.back() <= N) pw2.push_back(pw2.back() * 2);
	while (pw3.back() <= N) pw3.push_back(pw3.back() * 3);
	while (pw5.back() <= N) pw5.push_back(pw5.back() * 5);
	vector<vector<int> > g;
	for (int i = 0; i < pw2.size() && pw2[i] <= N; ++i) {
		for (int j = 0; j < pw3.size() && pw2[i] * pw3[j] <= N; ++j) {
			for (int k = 0; k < pw5.size() && pw2[i] * pw3[j] * pw5[k] <= N; ++k) {
				g.push_back({ i, j, k });
				g.push_back({ i + 1, j, k });
				g.push_back({ i, j + 1, k });
				g.push_back({ i, j, k + 1 });
			}
		}
	}
	sort(g.begin(), g.end());
	g.erase(unique(g.begin(), g.end()), g.end());
	int S = g.size();
	vector<long long> targetl(S), targetr(S);
	for (int i = 0; i < S; ++i) {
		int x = g[i][0], y = g[i][1], z = g[i][2];
		long long b = pw2[x] * pw3[y] * pw5[z];
		targetr[i] = N % b;
		targetl[i] = N % b - b;
	}
	vector<long long> dpl(S, inf), dpr(S, inf);
	dpl[0] = 1; dpr[0] = 0;
	for (int i = 1; i < S; ++i) {
		int x = g[i][0], y = g[i][1], z = g[i][2];
		long long b = pw2[x] * pw3[y] * pw5[z];
		if (x >= 1) {
			int ptr = lower_bound(g.begin(), g.end(), vector<int>({ x - 1, y, z })) - g.begin();
			dpl[i] = min({ dpl[i], dpl[ptr] + abs(targetl[ptr] - targetl[i]) / (b / 2), dpr[ptr] + abs(targetr[ptr] - targetl[i]) / (b / 2) });
			dpr[i] = min({ dpr[i], dpl[ptr] + abs(targetl[ptr] - targetr[i]) / (b / 2), dpr[ptr] + abs(targetr[ptr] - targetr[i]) / (b / 2) });
		}
		if (y >= 1) {
			int ptr = lower_bound(g.begin(), g.end(), vector<int>({ x, y - 1, z })) - g.begin();
			dpl[i] = min({ dpl[i], dpl[ptr] + abs(targetl[ptr] - targetl[i]) / (b / 3), dpr[ptr] + abs(targetr[ptr] - targetl[i]) / (b / 3) });
			dpr[i] = min({ dpr[i], dpl[ptr] + abs(targetl[ptr] - targetr[i]) / (b / 3), dpr[ptr] + abs(targetr[ptr] - targetr[i]) / (b / 3) });
		}
		if (z >= 1) {
			int ptr = lower_bound(g.begin(), g.end(), vector<int>({ x, y, z - 1 })) - g.begin();
			dpl[i] = min({ dpl[i], dpl[ptr] + abs(targetl[ptr] - targetl[i]) / (b / 5), dpr[ptr] + abs(targetr[ptr] - targetl[i]) / (b / 5) });
			dpr[i] = min({ dpr[i], dpl[ptr] + abs(targetl[ptr] - targetr[i]) / (b / 5), dpr[ptr] + abs(targetr[ptr] - targetr[i]) / (b / 5) });
		}
		if (dpr[i] - dpl[i] >= 2) dpr[i] = dpl[i] + 1;
		if (dpl[i] - dpr[i] >= 2) dpl[i] = dpr[i] + 1;
	}
	long long ans = inf;
	for (int i = 0; i < S; ++i) {
		int x = g[i][0], y = g[i][1], z = g[i][2];
		long long b = pw2[x] * pw3[y] * pw5[z];
		long long rem = (N - targetr[i]) / b;
		double respre = x * A + y * B + z * C + (1.0 * dpr[i] + rem) * D;
		if (respre < ans * 1.01) {
			long long res = x * A + y * B + z * C + (dpr[i] + rem) * D;
			ans = min(ans, res);
		}
	}
	return ans;
}
long long solve_easy(long long N, long long A, long long B, long long C, long long D) {
	vector<long long> dist(10 * N + 1, inf);
	dist[5 * N] = 0;
	priority_queue<pair<long long, long long> > que;
	que.push(make_pair(0, 0));
	vector<bool> vis(10 * N + 1, false);
	while (!que.empty()) {
		long long u = que.top().second; que.pop();
		if (vis[u + 5 * N]) continue;
		vis[u + 5 * N] = true;
		long long d = dist[u + 5 * N];
		if (abs(u * 2) <= 5 * N && dist[u * 2 + 5 * N] > d + A) {
			dist[u * 2 + 5 * N] = d + A;
			que.push(make_pair(-(d + A), u * 2));
		}
		if (abs(u * 3) <= 5 * N && dist[u * 3 + 5 * N] > d + B) {
			dist[u * 3 + 5 * N] = d + B;
			que.push(make_pair(-(d + B), u * 3));
		}
		if (abs(u * 5) <= 5 * N && dist[u * 5 + 5 * N] > d + C) {
			dist[u * 5 + 5 * N] = d + C;
			que.push(make_pair(-(d + C), u * 5));
		}
		if (abs(u + 1) <= 5 * N && dist[u + 1 + 5 * N] > d + D) {
			dist[u + 1 + 5 * N] = d + D;
			que.push(make_pair(-(d + D), u + 1));
		}
		if (abs(u - 1) <= 5 * N && dist[u - 1 + 5 * N] > d + D) {
			dist[u - 1 + 5 * N] = d + D;
			que.push(make_pair(-(d + D), u - 1));
		}
	}
	return dist[6 * N];
}
void random_gen() {
	bool found = false;
	for (int N = 1; N <= 100 && !found; ++N) {
		for (int rep = 1; rep <= 1000 && !found; ++rep) {
			long long A = rand_rng(1, 1000000000);
			long long B = rand_rng(1, 1000000000);
			long long C = rand_rng(1, 1000000000);
			long long D = rand_rng(1, 1000000000);
			long long res1 = solve(N, A, B, C, D);
			long long res2 = solve_easy(N, A, B, C, D);
			if (res1 != res2) {
				cout << "N = " << N << " / Case #" << rep << ":" << endl;
				cout << "A = " << A << ", B = " << B << ", C = " << C << ", D = " << D << endl;
				cout << "Returns: " << res1 << endl;
				cout << "Answer: " << res2 << endl;
				found = true;
			}
		}
	}
}
int main() {
	// random_gen();
	int Q;
	cin >> Q;
	while (Q--) {
		long long N, A, B, C, D;
		cin >> N >> A >> B >> C >> D;
		long long res = solve(N, A, B, C, D);
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 6028