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

map<ll, ll> dp;

ll N;
ll A, B, C, D;

ll rec(ll x)
{
	if(x == 0) return 0;
	if(x == 1) return D;
	if(dp.count(x)) return dp[x];
	ll l2 = (x/2)*2, r2=(x+1)/2*2;
	ll l3 = (x/3)*3, r3=(x+2)/3*3;
	ll l5 = (x/5)*5, r5=(x+4)/5*5;
	
	ll res = 1e18;
	if(x < res/D) res = x*D;
	res = min(res, llabs(l2-x)*D+A+rec(l2/2));
	res = min(res, llabs(r2-x)*D+A+rec(r2/2));
	
	res = min(res, llabs(l3-x)*D+B+rec(l3/3));
	res = min(res, llabs(r3-x)*D+B+rec(r3/3));
	
	res = min(res, llabs(l5-x)*D+C+rec(l5/5));
	res = min(res, llabs(r5-x)*D+C+rec(r5/5));
	
	return dp[x] = res;
}

void solve()
{
	dp.clear();
	cout << rec(N) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
	int t; cin >> t;
	while(t--){
		cin >> N >> A >> B >> C >> D;
		solve();
	}
	return 0;
}