#include <bits/stdc++.h>
using namespace std;

using ll = long long;
ll c2, c3, c5, c1;

map<ll, ll> memo;

ll solve(ll n){
	if(!memo.count(n)){
		if(n == 0){
			memo[n] = 0;
		} else {
			ll res = 7e18;
			if(n <= res / c1) res = min(res, c1 * n);
			res = min(res, solve(n / 2) + c2 + c1 * (n % 2));
			res = min(res, solve(n / 3) + c3 + c1 * (n % 3));
			res = min(res, solve(n / 5) + c5 + c1 * (n % 5));
			if(n > 1){
				if(n > 2) res = min(res, solve(1 + n / 2) + c2 + c1 * (2 - (n % 2)));
				res = min(res, solve(1 + n / 3) + c3 + c1 * (3 - (n % 3)));
				res = min(res, solve(1 + n / 5) + c5 + c1 * (5 - (n % 5)));
			}
			memo[n] = res;
		}
	}
	return memo[n];
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--){
		memo = {};
		ll n;
		cin >> n;
		cin >> c2 >> c3 >> c5 >> c1;
		ll ans = solve(n);
		cout << ans << '\n';
	}
}