#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int t, w[10], d;
ll n;
map<ll, ll> mp;

ll dfs(ll x) {
	if (!x) return 0;
	if (mp.count(x)) return mp[x];
	ll ans = min(__int128(x) * d, __int128(inf));
	for (int i = 2; i <= 5; ++i)
		if (i != 4) {
			ll v1 = x / i * i, v2 = ((x - 1) / i + 1) * i;
			if (v1 / i < x)
				ans = min(ans, dfs(v1 / i) + w[i] + (x - v1) * d);
			if (v2 / i < x)
				ans = min(ans, dfs(v2 / i) + w[i] + (v2 - x) * d);
		}
	return mp[x] = ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%lld", &n);
		scanf("%d%d%d%d", &w[2], &w[3], &w[5], &d);
		mp.clear();
		printf("%lld\n", dfs(n));
	}
}
