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

int t;
/*
long long int ds(long long int val,int d){
	long long int go=val/d;
	go+=min(val%d,d-(val%d));
}*/

int a,b,c,d;
map<long long int,long long int> s;
void f(long long int &a,long long int b){
	if(b<0LL)return;
	if(a<0LL)a=b;
	a=min(a,b);
}
int ar[]={2,3,5};
long long int cs[]={0,0,0};
inline long long  dfs(long long int val){
	if(val==0)return 0;
	if(s.count(val)){
		return s[val];
	}
	s[val]=10000000000000000LL;
	if(10000000000000000LL/d>=val){
		s[val]=val*d;
	}
	for(int i=0;i<3;i++){
		f(s[val],dfs(val/ar[i])+cs[i]+(val%ar[i])*d);
		f(s[val],dfs(val/ar[i]+1)+cs[i]+(ar[i]-(val%ar[i]))*d);
	}
return s[val];
}

int main(){
	
//	cout<<s.size()<<endl;
	cin>>t;
	while(t--){
		long long int n;
		cin>>n>>a>>b>>c>>d;
		cs[0]=a;
		cs[1]=b;
		cs[2]=c;
		s.clear();
		cout<<dfs(n)<<endl;
		
	}
	return 0;
}
