#include<cstdio>
#include<map>
#define Z int
#define V void
#define L long long
#define USE using namespace std
#define S(n) scanf("%lld",&n)
#define P(n) printf("%lld\n",n)
#define W while
#define sm(a,b) ((a)<(b)?(a):(b))
#define I if
#define R return
USE;
map<L,L>rem;
L t,n,a,b,c,d,lim=(L)(1e18),ans;
L dfs(L x){
	I(rem[x]||!x)R rem[x];
	rem[x]=lim;
	L y;
	y=x/2*2,rem[x]=sm(rem[x],dfs(y/2)+(x-y)*d+a);
	y=(x/2+1)*2,rem[x]=sm(rem[x],dfs(y/2)+(y-x)*d+a);
	y=x/3*3,rem[x]=sm(rem[x],dfs(y/3)+(x-y)*d+b);
	y=(x/3+1)*3,rem[x]=sm(rem[x],dfs(y/3)+(y-x)*d+b);
	y=x/5*5,rem[x]=sm(rem[x],dfs(y/5)+(x-y)*d+c);
	y=(x/5+1)*5,rem[x]=sm(rem[x],dfs(y/5)+(y-x)*d+c);
	I(x<=lim/d)rem[x]=sm(rem[x],x*d);
	R rem[x];
}
V doit(){S(n),S(a),S(b),S(c),S(d),rem.clear(),P(dfs(n));}
Z main(){
	S(t);
	W(t--)doit();
}