#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <map>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
ll T;
ll n, a, b, c, d;
map<ll, ll> mp;

ll dfs(ll x) {
	if (mp.count(x)) return mp[x];
	if (x == 0) return mp[0] = 0;
	if (x == 1) return mp[1] = d;

	ll res = INF;
	if (x <= n / d) res = min(res, x*d);
	res = min(res, dfs(x / 2) + a + x % 2 * d);
	res = min(res, dfs((x + 1) / 2) + a + (2 - x % 2)*d);
	res = min(res, dfs(x / 3) + b + x % 3 * d);
	res = min(res, dfs((x + 2) / 3) + b + (3 - x % 3)*d);
	res = min(res, dfs(x / 5) + c + x % 5 * d);
	res = min(res, dfs((x + 4) / 5) + c + (5 - x % 5)*d);
	return mp[x] = res;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n >> a >> b >> c >> d;
		mp.clear();
		cout << dfs(n) << endl;
	}

	return 0;
}
