/*input
5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
 
#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 100001
#define M 1000000007
#define pie 3.141592653589793238
#define ll long long
#define ld long double
#define vll vector<long long>
#define vi vector<int>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<long long,long long> >
#define pb push_back
#define pf pop_front
#define F first
#define S second
#define endl '\n'
 
using namespace std;
using namespace __gnu_pbds; 
 
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
 
ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}
 
 
void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}
 
ll a,b,c,d;
 
map<ll,ll> mp;
 
ll func(ll n){
	if(!n)return 0;
	if(n==1)return d;
	if(mp[n])return mp[n];
	ll ans=LLONG_MAX;
	if(n<(7*1e18)/d)ans=min(ans,n*d);
	if(n%2==0)ans=min(ans,a+func(n/2));
	else{
		ll k=n/2;
		k*=2;
		ans=min(ans,abs(n-k)*d+a+func(k/2));
		k+=2;
		ans=min(ans,abs(n-k)*d+a+func(k/2));
	}
	if(n%3==0)ans=min(ans,b+func(n/3));
	else{
		ll k=n/3;
		k*=3;
		ans=min(ans,abs(n-k)*d+b+func(k/3));
		k+=3;
		ans=min(ans,abs(n-k)*d+b+func(k/3));
	}
	if(n%5==0)ans=min(ans,c+func(n/5));
	else{
		ll k=n/5;
		k*=5;
		ans=min(ans,abs(n-k)*d+c+func(k/5));
		k+=5;
		ans=min(ans,abs(n-k)*d+c+func(k/5));
	}
	return mp[n]=ans;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	ll t=1,i,j;
	cin>>t;
	while(t--){
		ll n;
		cin>>n>>a>>b>>c>>d;
		mp.clear();
		cout<<func(n)<<endl;
	}
	return 0;
}
 
 