#include<stdio.h>
long long a,b,c,d,n,ans,mod5,mod3,mod2;
long long f[10000000];
int re[10000000];
int t,flag,j;
void search(long long n,long long cost){
	if (n==0) return;
	
	if (n<10000000){
		if (re[n]==0||cost<f[n]){
			f[n]=cost;
			re[n]=1;
		}else{
			return;
		}
	}
//	printf("%d\n",n);
	mod5=n % 5;
	search(n/5,cost+c+mod5*d);
	search(n/5+1,cost+c+(5-mod5)*d);
	mod3=n % 3;
	search(n/3,cost+b+mod3*d);
	search(n/3+1,cost+b+(3-mod3)*d);
	mod2=n % 2;
	search(n/2,cost+a+mod2*d);
	search(n/2+1,cost+a+(2-mod2)*d);
}
int main(){
	scanf("%d",&t);
	int i;
	for (i=1;i<=t;i++){
		flag=0;
		for (j=1;j<10000000;j++)
		  {re[j]=0;f[j]=0;
		  }
		scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&c,&d);
		search(n,0);
		printf("%lld\n",f[1]+d);
	}
} 