#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<map>

using namespace std;

#define int __int128
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

int N, A, B, C, D;

long long solve(){
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
	
	map<int,int> mp;
	
	Q.push({0,N});
	
	while(!Q.empty()){
		pair<int,int> p = Q.top(); Q.pop();
		int cost = p.first;
		int num = p.second;
		
		if(num == 0) return cost;
		
		if(mp.count(num) && mp[num] < cost) continue;
		
		// cout<<"num = "<<(long long)num<<" cost = "<<(long long)cost<<endl;
		
		{
			int al = (num/2), ah = ((num + 2 - 1)/2);
			// cout<<"al3 = "<<(long long)al<<" ah3 = "<<(long long)ah<<endl;
			if(mp.count(al)) {
				if(mp[al] > cost + A + abs(num - al*2) * D) {
					mp[al] = cost + A + abs(num - al*2) * D;
					Q.push({mp[al], al});
				}
			} else {
				mp[al] = cost + A + abs(num - al*2) * D;
				// cout<<"<> "<<(long long)mp[al]<<endl;
				Q.push({mp[al], al});
			}
			
			if(mp.count(ah)) {
				if(mp[ah] > cost + A + abs(num - ah*2) * D) {
					mp[ah] = cost + A + abs(num - ah*2) * D;
					Q.push({mp[ah], ah});
				}
			} else {
				mp[ah] = cost + A + abs(num - ah*2) * D;
				// cout<<"[] "<<(long long)mp[ah]<<endl;
				Q.push({mp[ah], ah});
			}
		
		}
		
		{ 
			int al = (num/3), ah = ((num + 3 - 1)/3);
			// cout<<"al3 = "<<(long long)al<<" ah3 = "<<(long long)ah<<endl;
			if(mp.count(al)) {
				if(mp[al] > cost + B + abs(num - al*3) * D) {
					mp[al] = cost + B + abs(num - al*3) * D;
					Q.push({mp[al], al});
				}
			} else { 
				mp[al] = cost + B + abs(num - al*3) * D;
				// cout<<"<> "<<(long long)mp[al]<<endl;
				Q.push({mp[al], al});
			}
			
			if(mp.count(ah)) {
				if(mp[ah] > cost + B + abs(num - ah*3) * D) {
					mp[ah] = cost + B + abs(num -  ah*3) * D;
					Q.push({mp[ah], ah});
				}
			} else {
				
				mp[ah] = cost + B + abs(num -  ah*3) * D;
				// cout<<"[] "<<(long long)mp[ah]<<endl;
				Q.push({mp[ah], ah});
			}
		
		}
		
		
		{
			int al = (num/5), ah = ((num + 5 - 1)/5);
			
			if(mp.count(al)) {
				if(mp[al] > cost + C + abs(num - al*5) * D) {
					mp[al] = cost + C + abs(num - al*5) * D;
					Q.push({mp[al], al});
				}
			} else {
				mp[al] = cost + C + abs(num - al*5) * D;
				Q.push({mp[al], al});
			}
			
			if(mp.count(ah)) {
				if(mp[ah] > cost + C + abs(num - ah*5) * D) {
					mp[ah] = cost + C + abs(num - ah*5) * D;
					Q.push({mp[ah], ah});
				}
			} else {
				mp[ah] = cost + C + abs(num - ah*5) * D;
				Q.push({mp[ah], ah});
			}
		
		}
		
		{
			int al = 0;
			
			if(mp.count(al)) {
				if(mp[al] > cost +  abs(num - al) * D) {
					mp[al] = cost + abs(num - al) * D;
					Q.push({mp[al], al});
				}
			} else {
				mp[al] = cost +  abs(num - al) * D;
				Q.push({mp[al], al});
			}

		
		}
	}
	
	return -1;
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	long long T;
	
	cin>>T;
	
	for(int _ = 0; _ < T; _++){

		long long  n, a, b, c, d;
		cin>>n>>a>>b>>c>>d;
		
		N = n;
		A = a;
		B = b;
		C = c;
		D = d;
		
		cout<<solve()<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 4588