#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll INF=9e18;
int T,cnt;
ll n,a,b,c,d;
map<ll,ll> M;
ll solve(ll x) {
	if (M[x]) return M[x];
	if (!x) return M[x]=0;
	M[x]=INF;
	if (x<INF/d) M[x]=x*d;
	if (x%2==0) M[x]=min(M[x],solve(x/2)+a);
	else M[x]=min(M[x],min(solve(x/2),solve(x/2+1))+a+d);
	ll y;
	if (x%3==0) M[x]=min(M[x],solve(x/3)+b);
	else {
		y=x/3;
		M[x]=min(M[x],min(solve(y)+(x%3)*d,solve(y+1)+(3-x%3)*d)+b);
	}
	if (x%5==0) M[x]=min(M[x],solve(x/5)+c);
	else {
		y=x/5;
		M[x]=min(M[x],min(solve(y)+(x%5)*d,solve(y+1)+(5-x%5)*d)+c);
	}
	cnt++;
	return M[x];
}
int main() {
	//freopen("1.txt","r",stdin);
	read(T);
	while (T--) {
		M.clear();
		read(n); read(a); read(b); read(c); read(d);
		cnt=0;
		printf("%lld\n",solve(n));
		//printf("cnt=%d\n",cnt);
	}
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/