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

#define Inf (long long)(1e18)

int T,a,b,c,d;
long long n;
map<long long,long long>f;

long long F(long long n){
	if(f.count(n))return f[n];
	if(n<=1)return 1LL*n*d;
	long long val=Inf;
	if(Inf/n>d)val=1LL*n*d;
	int c2=n%2,c3=n%3,c5=n%5;
	if(!c2)val=min(val,F(n/2)+a);
	else val=min(val,min(F((n+2-c2)/2)+a+1LL*(2-c2)*d,F((n-c2)/2)+a+1LL*c2*d));
	if(!c3)val=min(val,F(n/3)+b);
	else val=min(val,min(F((n+3-c3)/3)+b+1LL*(3-c3)*d,F((n-c3)/3)+b+1LL*c3*d));
	if(!c5)val=min(val,F(n/5)+c);
	else val=min(val,min(F((n+5-c5)/5)+c+1LL*(5-c5)*d,F((n-c5)/5)+c+1LL*c5*d));
	return f[n]=val;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);
		f.clear();
		printf("%lld\n",F(n));
	}
	return 0;
}