#include <cstdio>
#include <algorithm>
#include <unordered_map>

typedef long long LL;
const LL Infll = 0x3f3f3f3f3f3f3f3f;

LL A, B, C, D;
std::unordered_map<LL, LL> mp;
LL f(LL x) {
	if (x == 0) return 0;
	if (x == 1) return D;
	if (mp.count(x)) return mp[x];
	LL ret = x <= Infll / D ? x * D : Infll;
	ret = std::min(ret, x % 2 * D + A + f(x / 2));
	ret = std::min(ret, x % 3 * D + B + f(x / 3));
	ret = std::min(ret, x % 5 * D + C + f(x / 5));
	if (x % 2) ret = std::min(ret, (2 - x % 2) * D + A + f(x / 2 + 1));
	if (x % 3) ret = std::min(ret, (3 - x % 3) * D + B + f(x / 3 + 1));
	if (x % 5) ret = std::min(ret, (5 - x % 5) * D + C + f(x / 5 + 1));
	return mp[x] = ret;
}

int main() {
	int Tests;
	scanf("%d", &Tests);
	while (Tests--) {
		LL N;
		scanf("%lld%lld%lld%lld%lld", &N, &A, &B, &C, &D);
		mp.clear();
		printf("%lld\n", f(N));
	}
	return 0;
}