#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(lint)(n);i++)
#define REP(i,n) for(int i=1;i<=(lint)(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = 1e-9;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, unsigned int b) {
	if (!b)return T(1);
	if (b & 1)return mypow(a, b - 1) * a;
	T memo = mypow(a, b >> 1);
	return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
	if (!b)return 1;
	if (b & 1)return modpow(a, b - 1, m) * a % m;
	lint memo = modpow(a, b >> 1, m);
	return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
int t;
lint n,a,b,c,d;
prique<std::pair<std::pair<lint,bool>,lint>> que;
std::unordered_map<lint,lint> ans;
int main(){
	std::cin>>t;
	rep(i,t){
		ans.clear();
		std::cin>>n>>a>>b>>c>>d;
		que.push(std::make_pair(std::make_pair(0,true),n));
		while(!que.empty()){
			auto p=que.top();
			que.pop();
			if(ans[p.second]<p.first.first)continue;
			if(8e18/p.second>=d){
				if(ans.find(0)!=ans.end())chmin(ans[0],p.first.first+p.second*d);
				else ans[0]=p.first.first+p.second*d;
			}
			if(p.first.second){
				REP(i,10){
					if(ans.find(p.second+i)==ans.end()){
						ans[p.second+i]=p.first.first+i*d;
						que.push(std::make_pair(std::make_pair(p.first.first+i*d,false),p.second+i));
					}
					else if(chmin(ans[p.second+i],p.first.first+i*d)){
						que.push(std::make_pair(std::make_pair(p.first.first+i*d,false),p.second+i));
					}
					if(0<=p.second-i&&(ans.find(p.second-i)==ans.end()||chmin(ans[p.second-i],p.first.first+i*d))){
						ans[p.second-i]=p.first.first+i*d;
						que.push(std::make_pair(std::make_pair(p.first.first+i*d,false),p.second-i));
					}
				}
			}
			if(p.second%2==0&&(ans.find(p.second/2)==ans.end()||chmin(ans[p.second/2],p.first.first+a))){
				ans[p.second/2]=p.first.first+a;
				que.push(std::make_pair(std::make_pair(p.first.first+a,true),p.second/2));
			}
			if(p.second%3==0&&(ans.find(p.second/3)==ans.end()||chmin(ans[p.second/3],p.first.first+b))){
				ans[p.second/3]=p.first.first+b;
				que.push(std::make_pair(std::make_pair(p.first.first+b,true),p.second/3));
			}
			if(p.second%5==0&&(ans.find(p.second/5)==ans.end()||chmin(ans[p.second/5],p.first.first+c))){
				ans[p.second/5]=p.first.first+c;
				que.push(std::make_pair(std::make_pair(p.first.first+c,true),p.second/5));
			}
		}
		std::cout<<ans[0]<<"\n";
	}
	return 0;
}


Measured memory_bytes: 13212